The (Non-)Concentration of the Chromatic Number
summary
Proves that for G(n, 1/2) there are infinitely many n where the chromatic number is not contained in any interval of length n^{1/2 - ε}, matching known upper bounds up to a tiny exponent loss. Key tools are a planted independent-set coupling (embed G_n inside G_{n'} by randomly planting many maximum independent sets) and a Poisson/Stein approximation controlling the number of max independent sets; total-variation control ~1/√μ lets the gadget behave like G_{n'}. The construction succeeds and yields the non-concentration lower bound.
AI-written summary · about
chapters (12)
- 0:00Intro
- 5:23How about concentration?
- 10:32The opposite question
- 15:05Independent sets
- 17:23X, is not very sharply concentrated
- 19:35What does this have to do with colourings?
- 24:47First proof attempt
- 27:43Second proof attempt
- 30:23Key Lemma
- 36:22Proof ingredients
- 41:15So what's the truth?
- 44:42Open questions