Edge-statistics beyond 1 / e
Alexandr Grebennikov and Matthew Kwan · 2025
Read Edge-statistics beyond 1 / e by Alexandr Grebennikov and Matthew Kwan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-24691.txt.
Introduction
Alexandr Grebennikov and Matthew Kwan push past a known bound on how often a set edge count can show in large graphs. For sets of a fixed size, past work capped the share with a set count near a known constant. They ask when that cap can be cut if the edge count avoids a few tight cases.
For most edge counts, they show a strict smaller cap will do. When the edge count sits far from a whole count times the set size, their cap is much stronger and close to best. The work builds on past bounds and a kin result on graph form counts.
Catalog record
| CREATOR | Alexandr Grebennikov and Matthew Kwan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-24691
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Edge-statistics beyond 1 / e 1/e Thanks: Both authors are supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Alexandr Grebennikov and Matthew Kwan Abstract . For integers k k and ℓ \ell , let ind ( k , ℓ ) \ind(k,\ell) be the maximum proportion of k 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 → ∞ k\to\infty and 0 < ℓ < OPEN ( k 2 CLOSE ) 0<\ell<\binom{k}{2} , one has ind ( k , ℓ ) ⩽ 1 / e + o ( 1 ) \ind(k,\ell)\leqslant 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 ℓ ∈ { 1 , k − 1 , OPEN ( k 2 CLOSE ) − ( k − 1 ) , OPEN ( k 2 CLOSE ) − 1 } \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 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 ind ( k , ℓ ) \ind(k,\ell) when ℓ \ell is far from a multiple of k k , refining and extending previous bounds due to Fox and Sauermann. 1. Introduction For a k -vertex graph H , let N(n,H) be the maximum possible number of k -vertex subsets of an n -vertex graph that induce a copy of H . A simple averaging argument shows that N(n,H)/\binom{n}{k} is non-increasing in n , and thus one can define the inducibility of H as \ind(H)=\lim_{n\to\infty}\frac{N(n,H)}{\binom{n}{k}}. This concept was introduced by Pippenger and Golumbic [ 22 ] in 1975, and has been extensively studied since then. Alon, Hefetz, Krivelevich, and Tyomkyn [ 2 ] introduced the following variant of this notion. Let N(n,k,\ell) be the maximum number of k -vertex subsets of an n -vertex graph that induce exactly \ell edges. Similarly, N(n,k,\ell)/\binom{n}{k} is non-increasing in n , and one can define the edge-inducibility as \ind(k,\ell)=\lim_{n\to\infty}\frac{N(n,k,\ell)}{\binom{n}{k}}. Clearly, for each k we have \ind(k,0)=\ind(k,\binom{k}{2})=1 (since we can take the host graph to be empty or complete). Also note that \ind(k,\ell)=\ind(k,\binom{k}{2}-\ell) , since one can replace the host graph with its complement. Thus, throughout the rest of this introduction we restrict our attention to the range 1\leqslant\ell\leqslant\frac{1}{2}\binom{k}{2} . It follows from Goodman’s theorem that \ind(3,1)=3/4 . However, in general it is surprisingly difficult to determine edge-inducibilities exactly. For several small values of k and \ell , this was recently done by Bodnár and Pikhurko [ 4 ] via the method of flag algebras. Also, in this direction, Liu, Mubayi, and Reiher [ 17 , Theorem 1.13] obtained an explicit formula for \ind(k,1) , for all k . Alon, Hefetz, Krivelevich, and Tyomkyn suggested studying the asymptotic behaviour of edge-inducibilities as k\to\infty , and posed the following edge-statistics conjecture [ 2 , Conjecture 1.2] : if k is sufficiently large in terms of \varepsilon>0 and 1\leqslant\ell\leqslant\frac{1}{2}\binom{k}{2} , then (1) \ind(k,\ell)\leqslant 1/e+\varepsilon. This conjecture was proved in a combination of works by Kwan, Sudakov, and Tran [ 14 ] , Fox and Sauermann [ 10 ] , and Martinsson, Mousset, Noever, and Trujić [ 19 ] , and was recently extended to hypergraphs by Jain, Kwan, Mubayi, and Tran [ 11 ] . To see that the bound Equation 1 is asymptotically sharp, one can consider \ell=1 or \ell=k-1 . Indeed, suppose that k\to\infty , and that n is much larger than k . Then, • for \ell=1 , consider the random graph \mathbb{G}(n,\binom{k}{2}^{-1}) : the number of edges in its random k -vertex subgraph converges to a Poisson random variable with mean 1 ; • for \ell=k-1 , consider the complete bipartite graph K_{n/k,n-n/k} : the size of the intersection of a random k -subset of its vertices with the smaller part converges to a Poisson random variable with mean 1 . In this paper we investigate the “stability” of this problem: how can one improve the bound Equation 1 under additional assumptions on \ell ? Our first result states that for \ell\notin\{1,k-1\} , we can replace 1/e\approx 0.37 with a strictly smaller constant. Theorem 1.1 . Let k,\ell be positive integers such that k is sufficiently large, and 1\leqslant\ell\leqslant\frac{1}{2}\binom{k}{2} , \ell\notin\{1,k-1\} . Then, \ind(k,\ell)<0.33. This extends 1 1 1 Strictly speaking, our result as stated does not provide a bound on \ind(H) when H has exactly k-1 edges but is not a star. However, it follows from our proof that for such graphs \ind(H)\leqslant 2/e^{2}+o(1) . a recent result of Ueltzen [ 23 , Theorem 1.2] in the setting of graph inducibility, which states that for every k -vertex graph H such that 2\leqslant e(H)\leqslant\frac{1}{2}\binom{k}{2} and H\not\simeq K_{1,k-1} , one has \ind(H)\leqslant c+o(1) as k\to\infty for some c<1/e . Also, Theorem 1.1 confirms the uniformity-two case of a general conjecture due to Jain, Kwan, Mubayi, and Tran [ 11 ] on edge-inducibilities in hypergraphs (see Section 1.3 ). 1.1. Strong bounds when \ell is far from a small multiple of k Another interesting direction is to study assumptions on \ell that allow one to prove bounds of the form \ind(k,\ell)=o(1) as k\to\infty . For the “dense range”, i.e. when \ell/k\to\infty , an essentially optimal such bound was obtained by Kwan and Sauermann [ 13 ] (building upon the previous work of Kwan, Sudakov, and Tran [ 14 , Theorem 1.1] and Alon, Hefetz, Krivelevich, and Tyomkyn [ 2 , Theorem 1.5] ). Theorem 1.2 (Kwan–Sauermann [ 13 , Theorem 1.3] ) . Let k,\ell be positive integers such that 1\leqslant\ell\leqslant\frac{1}{2}\binom{k}{2} . Then, \ind(k,\ell)=O\mathopen{}\mathclose{{\left(\sqrt{k/\ell}}}\right). However, for \ell=O(k) this bound is vacuous. Fox and Sauermann [ 10 , Theorem 1.3] studied edge-inducibilities in the “very sparse” regime \ell\leqslant k/2 : they obtained an optimal bound of O(\ell^{-1/4}) for \ell\leqslant k/\log^{4}k , and a slightly suboptimal bound of O(k^{-1/4}\log k) for k/\log^{4}k\leqslant\ell\leqslant(1/2-o(1))k . In our next result, Theorem 1.3 , we refine these estimates by showing that the optimal bound O(\ell^{-1/4}) holds for all \ell\leqslant k-\sqrt{k} . In fact, more generally, we prove that an analogous statement is true for all values of \ell that are far from a multiple of k . Theorem 1.3 . Let k,\ell_{0},a be non-negative integers such that 1\leqslant\ell_{0}\leqslant k-1 and 0\leqslant a\leqslant\sqrt{k} . Then, \ind(k,ak+\ell_{0})=O\mathopen{}\mathclose{{\left(\max(\ell_{0}^{-1/4},((k-\ell_{0})/(a+1))^{-1/2})}}\right). In the range \ell=O(k) , this result is, in some sense, optimal (see Section 8.2 for a further discussion). On the other hand, while the bound from Theorem 1.3 still holds for a>\sqrt{k} , in this range it gets superseded by the bound from Theorem 1.2 . Figure 1. This cartoon plot summarises the upper bounds on \ind(k,\ell) given by Theorems 1.2 and 1.3 . 1.2. Asymptotic results when \ell is close to a small multiple of k Together, Theorems 1.2 and 1.3 imply that, for every \varepsilon>0 , we have \ind(k,\ell)\leqslant\varepsilon unless \ell=ak+b with 0\leqslant a\leqslant C and -C\leqslant b\leqslant C for some C=C(\varepsilon) . That is to say, \ind(k,\ell) is