Optimal anti-concentration conjecture for subgraph counts in random graphs

From papers

Fix p(0,1)p\in(0,1) and a graph HH with hh non-isolated vertices. Let GG(n,p)G\in\mathbb{G}(n,p) be a binomial random graph, and let XHX_H denote the number of copies of HH in GG. For any xNx\in\mathbb{N}, the optimal anti-concentration conjecture asserts

Pr(XH=x)=O\originalleft(1/Var(XH)\aftergroup\originalright)=O\originalleft(1/nh1\aftergroup\originalright).\Pr(X_H=x)=O\mathopen{}\mathclose\bgroup\originalleft(1/\sqrt{\operatorname{Var}(X_H)}\aftergroup\egroup\originalright)=O\mathopen{}\mathclose\bgroup\originalleft(1/n^{h-1}\aftergroup\egroup\originalright).

The paper states that the previously proved O(1/n)O(1/n) bound is far from optimal, motivating this stronger conjectural estimate. The source does not provide a resolution or a formal name for the conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Jacob Fox, Matthew Kwan and Lisa Sauermann, “Combinatorial anti-concentration inequalities, with applications”, arXiv:1905.12142 (2020).

Solutions 0

No solutions have been posted yet.