Theorem 4, p. 52 — for fixed 0 < p < 1, a.e. G(n,p) has n/s₀ ≤ χ ≤ (n/s₀)(1 + 3 log log n/log n)
ProvedBollobasChromatic.Main.theorem_4asymptoticschromatic-numberp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-graphs
Let be fixed and set , and
where is the integer part and is the natural logarithm. Then almost every random graph satisfies
that is, the probability that both inequalities hold tends to as .
This determines the chromatic number of the dense random graph asymptotically: almost surely, settling the factor- gap left by Grimmett and McDiarmid.
Formalization Note is Mathlib's chromatic number, finite on a finite vertex set and converted to a natural number. Both bounds are required of the same graph. does not depend on . For small the logarithms and take junk values; the statement is a limit and does not depend on them.
Preamble
import Mathlib import Definitions.Def_BollobasChromatic_Main_Setting
Formal statement
namespace BollobasChromatic.Main
open Filter Topology Asymptotics
theorem theorem_4 (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) :
AlmostEvery p (fun n G =>
(n : ℝ) / (s0 p n : ℝ) ≤ (G.chromaticNumber.toNat : ℝ) ∧
(G.chromaticNumber.toNat : ℝ) ≤
(n : ℝ) / (s0 p n : ℝ) * (1 + 3 * Real.log (Real.log (n : ℝ)) / Real.log (n : ℝ))) := by sorry
end BollobasChromatic.Main
Source
Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988), p. 52, Theorem 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.