Uniform anti-concentration conjecture for the independence number of sparse random graphs

About 4 years old · traced to

Let Gn,pG_{n,p} be the binomial random graph with nn vertices, where p=nγp=n^{\gamma} and −1<γ<−2/3-1<\gamma<-2/3, and let α(Gn,p)\alpha(G_{n,p}) denote its independence number. For an arbitrary sequence k=k(n)k=k(n), Uniform anti-concentration conjecture.

P(α(Gn,p)=k)=O~(n1+3γ/2).\mathbb{P}\left(\alpha(G_{n,p})=k\right)=\widetilde{O}\left(n^{1+3\gamma/2}\right).

This is proposed as a strengthening of the cited theorem and would give a uniform upper bound on every point probability in the regime −1<γ<−2/3-1<\gamma<-2/3; the supplied text gives no evidence that it has been resolved.

References

Primary source

Tom Bohman and Jakob Hofstad, “Two-Point Concentration of the Independence Number of the Random Graph”, arXiv:2208.00117 (2024).

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.