Corollary 1.2 — fractional chromatic counterexamples
OpenOAI.HadwigerCounterexample.corollary_1_2Corollary 1.2 of the source preprint (p. 3). There are finite nonempty simple graphs of arbitrarily large order for which
where is the Hadwiger number, the fractional chromatic number, and the chromatic number. Thus Hadwiger's conjecture and its fractional-coloring weakening (discussed by Reed and Seymour) are both false.
The lower bound follows by summing the vertex constraints of any fractional coloring and using ; the upper bound on is the matching–minor bound applied to the graphs of Theorem 1.1. The chain is stated for , where .
Formalization Note. Newly transcribed from the paper's Corollary 1.2 (the authors' bundled Lean theorem exists_counterexamples records the ordinary-chromatic chain but not the fractional term). Stated over ℝ; is fractionalChromaticNumber and is represented by the finite value chromaticNumber.toNat. This item should be compile-checked at submission.
import Mathlib import Definitions.Def_HadwigerMatching_Defs import Definitions.Def_ListHadwiger import Definitions.Def_HadwigerCounterexample_Fractional open OAI.HadwigerMatching OAI.LinearListHadwiger OAI.HadwigerCounterexample
namespace OAI.HadwigerCounterexample
theorem corollary_1_2 (M : ℕ) : ∃ m : ℕ, max M 5 ≤ m ∧
∃ G : SimpleGraph (Fin m),
(hadwigerNumber G : ℝ) < 26 * (m : ℝ) / 75 + 2 / 3 ∧
26 * (m : ℝ) / 75 + 2 / 3 < (m : ℝ) / 2 ∧
(m : ℝ) / 2 ≤ fractionalChromaticNumber G ∧
fractionalChromaticNumber G ≤ (G.chromaticNumber.toNat : ℝ) := by sorry
end OAI.HadwigerCounterexampleConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.