Paths of Odd Order in Graphs with Given Edge Density
We determine the asymptotic maximum number of unlabelled copies of $P_{2r+1}$ in graphs with prescribed edge density, where $r\ge1$ is fixed and $P_{2r+1}$ denotes the path on $2r+1$ vertices. If an $n$ vertex graph $G$ has edge density $c=2e(G)/n^2$, then the maximum is $\frac12S_r(c)n^{2r+1}+O(n^{2r})$ for $0<c\le c_r$, and $\frac12c^{r+1/2}n^{2r+1}+O(n^{2r})$ for $c_r\le c<1$, where $S_r(c)$ is the value given by the quasi-star construction and $c_r\in(0,1)$ is an explicit algebraic transition point. Thus the quasi-star construction is asymptotically extremal below the transition, while…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.05422
curl -X POST /api/v1/records/arxiv/2607.05422/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.05422/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'