The Edge-Statistics Conjecture for Hypergraphs

Let r,k, be integers such that 0≤ ≤ kr. Given a large r-uniform hypergraph G, we consider the fraction of k-vertex subsets that span exactly edges. If is $0$ or kr, this fraction can be exactly $1$ (by taking G to be empty or complete), but for all other values of , one might suspect that this fraction is always significantly smaller than $1$. In this paper we prove an essentially optimal result along these lines: if is not $0$ or kr, then this fraction is at most (1/e) + ε, assuming k is sufficiently large in terms of r and ε>0, and G is sufficiently large in terms of k. Previously, this was only known for a very limited range of values of r,k, (due to Kwan–Sudakov–Tran, Fox–Sauermann, and Martinsson–Mousset–Noever–Trujić). Our result answers a question of Alon–Hefetz–Krivelevich–Tyomkyn, who suggested this as a hypergraph generalization of their edge-statistics conjecture. We also prove a much stronger bound when is far from 0 and kr.