Erdős Problem #1156 — Non-concentration of the random-graph chromatic number

About 34 years old · traced to

For G∼G(n,1/2)G\sim G(n,1/2), can χ(G)\chi(G) be concentrated with high probability on a bounded number of values? More strongly, is there a function ω(n)→∞\omega(n)\to\infty such that for every deterministic f(n)f(n) one has

P(∣χ(G)−f(n)∣<ω(n))<1/2\mathbb{P}(|\chi(G)-f(n)|<\omega(n))<1/2

for all sufficiently large nn?

References

Additional references

A. Heckel and O. Riordan, How does the chromatic number of a random graph vary?, Journal of the London Mathematical Society 108 (2023), 1769–1815.

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.