/- 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.Powerset

The 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 0

The 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} := V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vv:Vhmem:{v} ∈ {S | v ∈ S}⊢ 1 = singletonWeights {v} All goals completed! 🐙 _ ≤ ∑ S ∈ (Finset.univ : Finset (Finset V)).filter (fun S => v ∈ S), singletonWeights S := Finset.single_le_sum (fun S _ => 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 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; 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 ≤ 1V: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 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 ≤ 1V: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 All goals completed! 🐙) hmem

The total weight of the singleton weighting is |V|.

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} = Finset.map { toFun := fun v ↦ {v}, inj' := ⋯ } Finset.univ 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 V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset V⊢ (∃ a, S = {a}) ↔ ∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = S V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset V⊢ (∃ a, S = {a}) → ∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = SV:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset V⊢ (∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = S) → ∃ a, S = {a} V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset V⊢ (∃ a, S = {a}) → ∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = SV:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset V⊢ (∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = S) → ∃ a, S = {a} V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset Va:Vha:{ toFun := fun v ↦ {v}, inj' := ⋯ } a = S⊢ ∃ a, S = {a} V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset Va:Vha:S = {a}⊢ ∃ a, { toFun := fun v ↦ {v}, inj' := ⋯ } a = SV:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VS:Finset Va:Vha:{ toFun := fun v ↦ {v}, inj' := ⋯ } a = S⊢ ∃ a, S = {a} 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 := V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vt:ℝht:t ∈ G.fractionalColoringWeights⊢ 0 ≤ t V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph Vw:Finset V → ℝhw:G.IsFractionalColoring w⊢ 0 ≤ ∑ S, w 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 := V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph V⊢ G.fractionalChromaticNumber ≤ ↑(Fintype.card V) V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq VG:SimpleGraph V⊢ ↑(Fintype.card V) ∈ G.fractionalColoringWeights All goals completed! 🐙end SimpleGraph