Edge-statistics beyond $1/e$
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911237228462080 |
|---|---|
| author | Grebennikov, Alexandr Kwan, Matthew |
| author_facet | Grebennikov, Alexandr Kwan, Matthew |
| contents | For integers $k$ and $\ell$, let $\operatorname{ind}(k, \ell)$ be the maximum proportion of $k$-vertex subsets of a large graph that induce exactly $\ell$ edges. The edge-statistics theorem (conjectured by Alon-Hefetz-Krivelevich-Tyomkyn, and proved by Kwan-Sudakov-Tran, Fox-Sauermann, and Martinsson-Mousset-Noever-Trujić) asserts that, for $k \to \infty$ and $0 < \ell <\binom{k}{2}$, one has $\operatorname{ind}(k, \ell) \le 1/e + o(1)$.
We investigate the ''stability'' of this problem: how can one improve this bound under additional assumptions on $\ell$? In particular, the edge-statistics theorem is tight when $\ell\in \{1,k-1,\binom{k}{2}-(k-1),\binom{k}{2}-1\}$; we show that for all other $\ell$, one can replace $1/e$ with a strictly smaller constant. This extends an analogous result of Ueltzen in the setting of graph inducibility. We also obtain a much stronger (and essentially optimal) upper bound on $\operatorname{ind}(k, \ell)$ when $\ell$ is far from a multiple of $k$, refining and extending previous bounds due to Fox and Sauermann. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_24691 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Edge-statistics beyond $1/e$ Grebennikov, Alexandr Kwan, Matthew Combinatorics For integers $k$ and $\ell$, let $\operatorname{ind}(k, \ell)$ be the maximum proportion of $k$-vertex subsets of a large graph that induce exactly $\ell$ edges. The edge-statistics theorem (conjectured by Alon-Hefetz-Krivelevich-Tyomkyn, and proved by Kwan-Sudakov-Tran, Fox-Sauermann, and Martinsson-Mousset-Noever-Trujić) asserts that, for $k \to \infty$ and $0 < \ell <\binom{k}{2}$, one has $\operatorname{ind}(k, \ell) \le 1/e + o(1)$. We investigate the ''stability'' of this problem: how can one improve this bound under additional assumptions on $\ell$? In particular, the edge-statistics theorem is tight when $\ell\in \{1,k-1,\binom{k}{2}-(k-1),\binom{k}{2}-1\}$; we show that for all other $\ell$, one can replace $1/e$ with a strictly smaller constant. This extends an analogous result of Ueltzen in the setting of graph inducibility. We also obtain a much stronger (and essentially optimal) upper bound on $\operatorname{ind}(k, \ell)$ when $\ell$ is far from a multiple of $k$, refining and extending previous bounds due to Fox and Sauermann. |
| title | Edge-statistics beyond $1/e$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.24691 |