Local concentration of subgraph counts in G(n,p)

Conjecture 1.12 · arXiv:1905.12142

arXiv Conjecture high confidence— first stated 2020-11-18

Authors: Jacob Fox, Matthew Kwan, Lisa Sauermann

Status disproved high confidence

The universal conjecture is false: for H = 2K2 there are x_n with Pr(X_H = x_n) = Omega(n^{-5/2}), whereas Var(X_H) = Theta(n^6), so the conjecture would require O(n^{-3}).

Cited literature (3)

counterexample Combinatorial anti-concentration inequalities, with applications (2019)

See linked article · Existing literature or final source version

The universal conjecture is false: for H = 2K2 there are x_n with Pr(X_H = x_n) = Omega(n^{-5/2}), whereas Var(X_H) = Theta(n^6), so the conjecture would require O(n^{-3}).

Read the literature-status audit
partial Anti-concentration for subgraph counts in random graphs (2021)

Jacob Fox, Matthew Kwan, Lisa Sauermann · Annals of Probability · arXiv:1905.12749 · doi:10.1214/20-AOP1490

Proves that for connected H with h vertices, Pr(X_H = x) <= n^{1-h+o(1)}, giving a near-optimal (but not tight) bound falling just short of the conjectured O(1/n^{h-1}); this is a companion paper submitted to arXiv concurrently in May 2019.
partial Local limit theorems for subgraph counts (2022)

Ashwin Sah, Mehtaab Sawhney · Journal of the London Mathematical Society · arXiv:2006.11369 · doi:10.1112/jlms.12523

Proves a local CLT for connected subgraph counts in G(n,p) (establishing the optimal O(1/n^{h-1}) bound of Conjecture 1.12 for connected H), while also providing a counterexample showing the conjectured bound fails for certain disconnected graphs, resolving the conjecture negatively in full generality.

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: The counterexample below is self-contained for ordinary non-induced subgraph counts; the positive connected case is cited rather than reproved.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

Conjecture. Fix $p \in (0,1)$ and fix a graph $H$ with $h$ non-isolated vertices. Let $G \in G(n,p)$. Then for any $x \in \mathbb{N}$, $$\Pr(X_H = x) = O\!\left(1/\sqrt{\mathrm{Var}(X_H)}\right) = O\!\left(1/n^{h-1}\right).$$

Context

The authors establish via Corollary 1.11 that $\Pr(X_H = x) = O(1/\sqrt{r})$ where $r$ is the number of edge-disjoint copies of $H$ in $G$, giving $O(1/n)$ in $G(n,p)$, but believe this is far from optimal. The conjectured bound matches the Gaussian scale and is best-possible given the known CLT for $X_H$. Theorem 1.14 confirms the conjecture for cliques $H = K_h$.

Source paper

Combinatorial anti-concentration inequalities, with applications
Jacob Fox, Matthew Kwan, Lisa Sauermann · 2020-11-18
https://arxiv.org/abs/1905.12142 PDF source