/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import Mathlib.Algebra.Order.Archimedean.Real.Basic
public import Mathlib.Algebra.BigOperators.Group.Finset.Basic
public import Mathlib.Algebra.Order.BigOperators.Group.Finset
public import Mathlib.Combinatorics.SimpleGraph.Clique
public import Mathlib.Data.Fintype.PowersetThe fractional chromatic number
A fractional colouring of a finite graph G assigns a nonnegative real weight to every
independent set so that every vertex receives total weight at least 1; the fractional
chromatic number χ_f(G) is the infimum of the total weights of fractional colourings. This is
the linear-programming relaxation of the chromatic number. Mathlib (as of 2026-08) has no such
notion.
We prove that the singleton weighting is a fractional colouring, so that χ_f(G) ≤ |V|, and
that χ_f(G) ≥ 0.
@[expose] public sectionnamespace SimpleGraphvariable {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
w is a fractional colouring of G: nonnegative weights supported on independent sets,
covering every vertex with total weight at least 1.
structure IsFractionalColoring (w : Finset V → ℝ) : Prop where
nonneg : ∀ S, 0 ≤ w S
indep : ∀ S, w S ≠ 0 → G.IsIndepSet (S : Set V)
cover : ∀ v, 1 ≤ ∑ S ∈ (Finset.univ : Finset (Finset V)).filter (fun S => v ∈ S), w S
The set of total weights of fractional colourings of G.
def fractionalColoringWeights : Set ℝ :=
{t | ∃ w : Finset V → ℝ, G.IsFractionalColoring w ∧ ∑ S, w S = t}
The fractional chromatic number χ_f(G).
noncomputable def fractionalChromaticNumber : ℝ :=
sInf (fractionalColoringWeights G)
The weighting giving weight 1 to every singleton (and 0 elsewhere).
def singletonWeights : Finset V → ℝ := fun S => if S.card = 1 then 1 else 0The singleton weighting is a fractional colouring.
V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vv:Vhmem:{v} ∈ {S | v ∈ S}⊢ 1 ≤ ∑ S with v ∈ S, singletonWeights S
calc (1 : ℝ) = singletonWeights {v} := by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vv:Vhmem:{v} ∈ {S | v ∈ S}⊢ 1 = singletonWeights {v} simp [singletonWeights] All goals completed! 🐙
_ ≤ ∑ S ∈ (Finset.univ : Finset (Finset V)).filter (fun S => v ∈ S), singletonWeights S :=
Finset.single_le_sum (fun S _ => by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vv:Vhmem:{v} ∈ {S | v ∈ S}S:Finset Vx✝:S ∈ {S | v ∈ S}⊢ 0 ≤ singletonWeights S unfold singletonWeights V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vv:Vhmem:{v} ∈ {S | v ∈ S}S:Finset Vx✝:S ∈ {S | v ∈ S}⊢ 0 ≤ if S.card = 1 then 1 else 0; split_ifs pos V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vv:Vhmem:{v} ∈ {S | v ∈ S}S:Finset Vx✝:S ∈ {S | v ∈ S}h✝:S.card = 1⊢ 0 ≤ 1neg V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vv:Vhmem:{v} ∈ {S | v ∈ S}S:Finset Vx✝:S ∈ {S | v ∈ S}h✝:¬S.card = 1⊢ 0 ≤ 0 <;> pos V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vv:Vhmem:{v} ∈ {S | v ∈ S}S:Finset Vx✝:S ∈ {S | v ∈ S}h✝:S.card = 1⊢ 0 ≤ 1neg V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vv:Vhmem:{v} ∈ {S | v ∈ S}S:Finset Vx✝:S ∈ {S | v ∈ S}h✝:¬S.card = 1⊢ 0 ≤ 0 norm_num All goals completed! 🐙) hmem
The total weight of the singleton weighting is |V|.
theorem sum_singletonWeights : ∑ S : Finset V, singletonWeights S = Fintype.card V := by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ∑ S, singletonWeights S = ↑(Fintype.card V)
unfold singletonWeights V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (∑ S, if S.card = 1 then 1 else 0) = ↑(Fintype.card V)
rw [Finset.sum_ite, V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ∑ x with x.card = 1, 1 + ∑ x with ¬x.card = 1, 0 = ↑(Fintype.card V) V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ↑{x | x.card = 1}.card = ↑(Fintype.card V) Finset.sum_const_zero, V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ∑ x with x.card = 1, 1 + 0 = ↑(Fintype.card V) V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ↑{x | x.card = 1}.card = ↑(Fintype.card V) add_zero, V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ∑ x with x.card = 1, 1 = ↑(Fintype.card V) V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ↑{x | x.card = 1}.card = ↑(Fintype.card V) Finset.sum_const, V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ {x | x.card = 1}.card • 1 = ↑(Fintype.card V) V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ↑{x | x.card = 1}.card = ↑(Fintype.card V) nsmul_eq_mul, V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ↑{x | x.card = 1}.card * 1 = ↑(Fintype.card V) V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ↑{x | x.card = 1}.card = ↑(Fintype.card V) mul_one V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ↑{x | x.card = 1}.card = ↑(Fintype.card V) V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ↑{x | x.card = 1}.card = ↑(Fintype.card V)] V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ ↑{x | x.card = 1}.card = ↑(Fintype.card V)
congr 1 V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ {x | x.card = 1}.card = Fintype.card V
rw [← Finset.card_univ, V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ {x | x.card = 1}.card = Finset.univ.card V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ {x | x.card = 1}.card = (Finset.map { toFun := fun v ↦ {v}, inj' := ⋯ } Finset.univ).card
← Finset.card_map ⟨fun v => ({v} : Finset V), fun _ _ h => Finset.singleton_injective h⟩ V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ {x | x.card = 1}.card = (Finset.map { toFun := fun v ↦ {v}, inj' := ⋯ } Finset.univ).card V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ {x | x.card = 1}.card = (Finset.map { toFun := fun v ↦ {v}, inj' := ⋯ } Finset.univ).card] V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ {x | x.card = 1}.card = (Finset.map { toFun := fun v ↦ {v}, inj' := ⋯ } Finset.univ).card
congr 1 V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ {x | x.card = 1} = Finset.map { toFun := fun v ↦ {v}, inj' := ⋯ } Finset.univ
ext S V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset V⊢ S ∈ {x | x.card = 1} ↔ S ∈ Finset.map { toFun := fun v ↦ {v}, inj' := ⋯ } Finset.univ
simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_map, Finset.card_eq_one] V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset V⊢ (∃ a, S = {a}) ↔ ∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = S
constructor mp V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset V⊢ (∃ a, S = {a}) → ∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = Smpr V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset V⊢ (∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = S) → ∃ a, S = {a} <;> mp V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset V⊢ (∃ a, S = {a}) → ∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = Smpr V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset V⊢ (∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = S) → ∃ a, S = {a} rintro ⟨a, ha⟩ mpr V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset Va:Vha:{ toFun := fun v ↦ {v}, inj' := ⋯ } a = S⊢ ∃ a, S = {a} <;> mp V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset Va:Vha:S = {a}⊢ ∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = Smpr V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset Va:Vha:{ toFun := fun v ↦ {v}, inj' := ⋯ } a = S⊢ ∃ a, S = {a} exact ⟨a, ha.symm⟩ All goals completed! 🐙There is at least one fractional colouring.
theorem fractionalColoringWeights_nonempty : (fractionalColoringWeights G).Nonempty :=
⟨_, singletonWeights, G.isFractionalColoring_singletonWeights, rfl⟩Total weights of fractional colourings are nonnegative.
theorem fractionalColoringWeights_nonneg {t : ℝ} (ht : t ∈ fractionalColoringWeights G) : 0 ≤ t := by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vt:ℝht:t ∈ G.fractionalColoringWeights⊢ 0 ≤ t
obtain ⟨w, hw, rfl⟩ := ht V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vw:Finset V → ℝhw:G.IsFractionalColoring w⊢ 0 ≤ ∑ S, w S
exact Finset.sum_nonneg fun S _ => hw.nonneg S All goals completed! 🐙
χ_f(G) ≥ 0.
theorem fractionalChromaticNumber_nonneg : 0 ≤ G.fractionalChromaticNumber :=
Real.sInf_nonneg fun _ ht => G.fractionalColoringWeights_nonneg ht
The trivial upper bound χ_f(G) ≤ |V|.
theorem fractionalChromaticNumber_le_card : G.fractionalChromaticNumber ≤ Fintype.card V := by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph V⊢ G.fractionalChromaticNumber ≤ ↑(Fintype.card V)
refine csInf_le ⟨0, fun _ ht => G.fractionalColoringWeights_nonneg ht⟩ ?_ V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph V⊢ ↑(Fintype.card V) ∈ G.fractionalColoringWeights
exact ⟨singletonWeights, G.isFractionalColoring_singletonWeights, sum_singletonWeights⟩ All goals completed! 🐙end SimpleGraph