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

Status partial high confidence

Conjecture 1.12 (that Pr(X_H = x) = O(1/sqrt(Var(X_H))) = O(1/n^{h-1}) for any fixed graph H with h non-isolated vertices in G(n,p)) has been resolved affirmatively for connected graphs H by Sah and Sawhney (arXiv:2006.11369, JLMS 2022), who established a local CLT for connected subgraph counts achieving the optimal scale. However, the same paper provides a counterexample showing the bound fails for certain disconnected graphs H, so the conjecture as stated for all graphs with non-isolated vertices is disproved. A companion paper (arXiv:1905.12749, Ann. Prob. 2021) by the same authors proved the near-optimal bound O(n^{1-h+o(1)}) for connected H, confirming the conjecture up to a subpolynomial factor.

Cited literature (2)

• 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. Conjecture 1.12 is proved for connected H (full optimal bound O(1/n^{h-1}) via local CLT, Sah-Sawhney 2022) and disproved for disconnected H with no isolated vertices. The companion paper 1905.12749 achieves a near-optimal bound n^{1-h+o(1)} for connected H. The paper itself (Theorem 1.14) confirms the conjecture for cliques. Status 'partial' reflects that the positive case (connected H) is fully resolved at the optimal scale.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).