Proofs of Two Conjectures of Alon on Subgraph Counts

Abstract

All graphs considered are finite with no isolated vertices. Let $N(m,H)$ be the maximum number of subgraphs of a graph $G$ isomorphic to $H$, taken over all graphs $G$ with $m$ edges. Alon proved that $N(m,H)={\Theta }_H(m^{\gamma (H)})$, where $\gamma (H)=(|V(H)|+D(H))/2$ and $D(H)={\max }_{S\subseteq V(H)}(|S|-|N_H(S)|)$, and conjectured [Conjecture 1, Isr. J. Math., 1986] that limit of $N(m,H)/m^{\gamma (H)}$ exists as $m\to \infty$. We prove this conjecture and identify the limit as $\lambda (H)=\Lambda (H)/|\mathrm{Aut}(H)|$, where $\Lambda (H)$ is characterized by a variational problem over finite cores. We also resolve another conjecture of Alon [Conjecture 2, Isr. J. Math., 1986], which stated that if $H$ is a disjoint union of stars, then for every $m$ an extremal graph attaining $N(m,H)$ may be chosen to be a disjoint union of stars.

16 pages; comments are welcome