← All problems

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

34 years old · traced to

For each positive integer nn, let Gn∼G(n,1/2)G_n\sim G(n,1/2) be the random graph on nn labelled vertices in which each possible edge is present independently with probability 1/21/2, and let χ(Gn)\chi(G_n) be its chromatic number. A sequence of events holds with high probability if its probability tends to 11 as n→∞n\to\infty. The first question is whether there are a constant CC and deterministic sets An⊆ZA_n\subseteq\mathbb Z with ∣An∣≤C|A_n|\le C such that

P(χ(Gn)∈An)⟶1.\mathbb P\bigl(\chi(G_n)\in A_n\bigr)\longrightarrow 1.

Erdős Problems #1156 How does the chromatic number of a random graph vary?

The stronger proposed assertion asks whether there is a sufficiently slowly diverging deterministic function ω:N→(0,∞)\omega:\mathbb N\to(0,\infty) such that, for every deterministic function f:N→Rf:\mathbb N\to\mathbb R, the inequality

P(∣χ(Gn)−f(n)∣<ω(n))<12\mathbb P\bigl(|\chi(G_n)-f(n)|<\omega(n)\bigr)<\frac12

holds for all sufficiently large nn. Erdős Problems #1156

Background

The chromatic number measures the minimum number of mutually nonadjacent vertex classes needed to partition a graph. Its typical value in random graphs has long been studied; the question of how much that value fluctuates is more delicate. Erdős and Rényi raised the typical-value question in the sparse setting, and Erdős later posed it for dense random graphs. For the uniform random graph, Bollobás proved the first-order asymptotic χ(Gn)∼n/(2log⁡2n)\chi(G_n)\sim n/(2\log_2 n) with high probability. The concentration problem asks not for this leading scale, but for the width of the distribution around typical values. Erdős Problems #1156 How does the chromatic number of a random graph vary?

Shamir and Spencer showed that, for any edge-probability function p=p(n)p=p(n), the chromatic number of G(n,p)G(n,p) is with high probability contained in an interval of length on the order of n\sqrt n. For constant p>0p>0, Alon improved the upper bound to order n/log⁡n\sqrt n/\log n. These upper bounds make the lower-bound question meaningful: despite concentration on a scale much narrower than the typical value, the distribution might still require intervals whose widths grow with nn. Erdős Problems #1156 How does the chromatic number of a random graph vary?

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.

Source: 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.