Anticoncentration conjecture for subgraph counts in random graphs

Let GG(n,p)G\sim G(n,p), where p(0,1)p\in(0,1) is fixed, and let XHX_H denote the number of copies of a fixed graph HH in GG. Assume that HH has no isolated vertices, and write v(H)v(H) for its number of vertices.

Anticoncentration conjecture.

maxxNPr(XH=x)=O\originalleft(n1v(H)\aftergroup\originalright).\max_{x\in\mathbb{N}}\Pr(X_H=x)=O\mathopen{}\mathclose\bgroup\originalleft(n^{1-v(H)}\aftergroup\egroup\originalright).

This conjecture proposes the optimal-order uniform upper bound for point probabilities of subgraph counts. Earlier work gives the weaker bound n1+o(1)n^{-1+o(1)} for graphs containing an edge; the conjectured estimate remains the sharper target in general.

Sources & referencesView supporting material

Primary source

Jacob Fox, Matthew Kwan and Lisa Sauermann, “Anticoncentration for subgraph counts in random graphs”, arXiv:1905.12749 (2020).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.