Theorem 9.1 —
ProvedTalagrandConc.Chromatic.theorem_9_1Let be the random graph on in which each of the possible edges , , is present with probability , , independently of the others. For let be the chromatic number of the subgraph induced on , and .
Let and be natural numbers and . Then there exists an integer such that
The theorem says that is concentrated on an interval of consecutive integers, up to an error plus the probability that some set of at most vertices already needs more than colours. The last term vanishes when , and remains small for smaller when .
Formalization Note is realised as the graph of a configuration under the product of Bernoulli() laws. The hypothesis is implicit on the page ( is an infimum over -subsets of ); without it and the statement fails. The integer may depend on . Probabilities are real numbers (Measure.real), so the right-hand side may be negative, as on the page.
import Mathlib import Definitions.Def_TalagrandConc_Chromatic_Basic open MeasureTheory open scoped Classical
namespace TalagrandConc.Chromatic
theorem theorem_9_1 (n m k : ℕ) (p t : ℝ) (hp0 : 0 < p) (hp1 : p < 1) (ht : 0 < t)
(hm : m ≤ n) :
∃ a : ℤ,
1 - 2 * Real.exp (-t ^ 2 / 8)
- (gnp n p).real {x | (k : ℕ∞) < localSup (graphOf x) (t * Real.sqrt m)}
≤ (gnp n p).real {x | (((a - k : ℤ)) : WithTop ℤ) ≤ chiMZ (graphOf x) m ∧
chiMZ (graphOf x) m ≤ (a : WithTop ℤ)} := by sorry
end TalagrandConc.Chromatic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.