Submit progress

on Erdős #1156 · graph theory / chromatic number

The statement

Let $G$ be a random graph on $n$ vertices, in which every edge is included independently with probability $1/2$ .

Is there some constant $C$ such that that chromatic number $\chi(G)$ is, almost surely, concentrated on at most $C$ values?

Is it true that, if $\omega(n)\to \infty$ sufficiently slowly, then for every function $f(n)$

\mathbb{P}(\lvert\chi(G)-f(n)\rvert<\omega(n))<1/2

if $n$ is sufficiently large?

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.