Variance-based anti-concentration conjecture for edge counts in Ramsey graphs

Let C,c>0C,c>0 be fixed constants. Let GG be an nn-vertex CC-Ramsey graph, meaning that GG has no clique or independent set of size ClognC\log n. Let kk satisfy

cnk(1c)n,cn\le k\le (1-c)n,

and let XX be the number of edges induced by a uniformly random kk-vertex subset of GG.

Variance-based anti-concentration conjecture. For every xZx\in\mathbb{Z},

Pr(X=x)=O\originalleft(1VarX\aftergroup\originalright).\Pr(X=x)=O\mathopen{}\mathclose\bgroup\originalleft(\frac{1}{\sqrt{\operatorname{Var} X}}\aftergroup\egroup\originalright).

This would give an optimal point-probability bound in terms of the variance, as suggested by Chebyshev's inequality. The statement is presented as an interesting open direction for Ramsey graphs.

Sources & referencesView supporting material

Primary source

Matthew Kwan and Lisa Sauermann, “An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs”, arXiv:1909.02089 (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.