Paperlane

no. 17 · Wednesday 18 November 2026

Subhypergraph counts and proofs of two conjectures of Alon

Peiru Kuang, Shuang Sun, Yan Wang and Jiasheng Zeng

math.CO · v2 · 24 pp

Abstract

For a fixed integer $r\ge2$ and a finite simple $r$-uniform hypergraph $H$ without isolated vertices, let $N_r(m,H)$ be the maximum number of unlabelled copies of $H$ among all finite simple $r$-uniform hypergraphs with $m$ edges. Friedgut and Kahn [Isr. J. Math., 1998] proved that $N_r(m,H)=Θ_H(m^{ρ^*(H)})$, where $ρ^*(H)$ is the fractional edge-cover number of $H$. We sharpen this to $N_r(m,H)=(λ_r(H)+o(1))m^{ρ^*(H)}$ as $m\to\infty$, with $λ_r(H)>0$, and characterize the limiting $λ_r(H)$ by a variational problem over finite hypergraphs. We develop a globally rainbow compression argument combining color-coding with successive vertex cloning. In particular, when $r=2$, the asymptotic formula confirms a conjecture of Alon [Isr. J. Math., Conjecture 1, 1986]. Moreover, for graphs we express the limiting constant $λ_2(H)$ as a supremum over finite cores. We also prove that, for every prescribed number of edges, an extremal graph for a star forest can be chosen to be a star forest, confirming another conjecture of Alon [Isr. J. Math., Conjecture 2, 1986].

comments
24 pages. This version extends the main asymptotic counting result from graphs to uniform hypergraphs. Comments are welcome
fields
Combinatorics
pdf ↗ page arXiv:2606.18321 ↗