Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2506.19061 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908418740060160 |
|---|---|
| author | English, Sean Spiro, Sam |
| author_facet | English, Sean Spiro, Sam |
| contents | A rational number $r$ is a \textbf{realizable exponent} for a graph $H$ if there exists a finite family of graphs $\mathcal{F}$ such that $\mathrm{ex}(n,H,\mathcal{F})=Θ(n^r)$, where $\mathrm{ex}(n,H,\mathcal{F})$ denotes the maximum number of copies of $H$ that an $n$-vertex $\mathcal{F}$-free graph can have. Results for realizable exponents are currently known only when $H$ is either a star or a clique, with the full resolution of the $H=K_2$ case being a major breakthrough of Bukh and Conlon.
In this paper, we establish the first set of results for realizable exponents which hold for arbitrary graphs $H$ by showing that for any graph $H$ with maximum degree $Δ\ge 1$, every rational in the interval $\left[v(H)-\frac{e(H)}{2Δ^2},\ v(H)\right]$ is realizable for $H$. We also prove a ``stability'' result for generalized Turán numbers of trees which implies that if $T\ne K_2$ is a tree with $\ell$ leaves, then $T$ has no realizable exponents in $[0,\ell]\setminus \mathbb{Z}$. Our proof of this latter result uses a new variant of the classical Helly theorem for trees, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19061 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rational Exponents for General Graphs English, Sean Spiro, Sam Combinatorics A rational number $r$ is a \textbf{realizable exponent} for a graph $H$ if there exists a finite family of graphs $\mathcal{F}$ such that $\mathrm{ex}(n,H,\mathcal{F})=Θ(n^r)$, where $\mathrm{ex}(n,H,\mathcal{F})$ denotes the maximum number of copies of $H$ that an $n$-vertex $\mathcal{F}$-free graph can have. Results for realizable exponents are currently known only when $H$ is either a star or a clique, with the full resolution of the $H=K_2$ case being a major breakthrough of Bukh and Conlon. In this paper, we establish the first set of results for realizable exponents which hold for arbitrary graphs $H$ by showing that for any graph $H$ with maximum degree $Δ\ge 1$, every rational in the interval $\left[v(H)-\frac{e(H)}{2Δ^2},\ v(H)\right]$ is realizable for $H$. We also prove a ``stability'' result for generalized Turán numbers of trees which implies that if $T\ne K_2$ is a tree with $\ell$ leaves, then $T$ has no realizable exponents in $[0,\ell]\setminus \mathbb{Z}$. Our proof of this latter result uses a new variant of the classical Helly theorem for trees, which may be of independent interest. |
| title | Rational Exponents for General Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.19061 |