Fractional chromatic number
DefinitionHadwigerCounterexample_FractionalThe fractional chromatic number of a finite simple graph is the minimum total weight of a fractional coloring. A fractional coloring assigns a nonnegative real weight to each independent vertex set so that every vertex is covered to total weight at least one:
An ordinary coloring gives a fractional coloring with unit weights on its color classes, so ; summing the vertex constraints gives . The source preprint (p. 3) uses this quantity to state its fractional-coloring counterexamples (Corollary 1.2).
Formalization Note. Weights are placed on all finite vertex sets (Finset V), with non-independent sets forced to weight zero; the infimum is a real-valued sInf. This matches the formalization already used on the platform for the Reed–Seymour theorem (OAI.LinearListHadwiger.Fractional.fractional_chromatic_le_two_hadwiger).
import Mathlib
namespace OAI
namespace HadwigerCounterexample
variable {V : Type} [Fintype V] [DecidableEq V]
/-- The fractional chromatic number: the infimum of the total weight of a
fractional coloring, i.e. nonnegative weights on independent vertex sets covering
each vertex to total at least one. Weights are placed on all finite vertex sets,
with non-independent sets forced to weight zero. -/
noncomputable def fractionalChromaticNumber (G : SimpleGraph V) : ℝ :=
sInf {c : ℝ | ∃ μ : Finset V → ℝ,
((∀ I, 0 ≤ μ I) ∧ (∀ I, ¬(∀ v ∈ I, ∀ u ∈ I, ¬G.Adj v u) → μ I = 0) ∧
∀ v, 1 ≤ ∑ I, if v ∈ I then μ I else 0) ∧ ∑ I, μ I = c}
end HadwigerCounterexample
end OAI
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.