/- 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 FormalConjecturesUtil

Erdős Problem 19

The Erdős–Faber–Lovász conjecture: if $G$ is an edge-disjoint union of $n$ copies of $K_n$, is $\chi(G) = n$?

We model $G$ by a family of $n$ vertex sets of size $n$ (the copies of $K_n$) which pairwise share at most one vertex and which cover the vertex type. Two copies of $K_n$ are edge-disjoint exactly when their vertex sets share at most one vertex.

References:

    erdosproblems.com/19

    [Hi81] Hindman, N., On a conjecture of Erdős, Faber, and Lovász about $n$-colorings. Canad. J. Math. (1981).

    [Ka92] Kahn, J., Coloring nearly-disjoint hypergraphs with $n + o(n)$ colors. J. Combin. Theory Ser. A (1992).

    [KKKMO21] Kang, D. Y., Kelly, T., Kühn, D., Methuku, A. and Osthus, D., A proof of the Erdős–Faber–Lovász conjecture. Ann. of Math. (2023). arXiv:2101.04698

@[expose] public sectionopen Filternamespace Erdos19open scoped Classical in

A configuration of n pairwise edge-disjoint copies of $K_n$ covering the vertex type V.

structure EFLConfig (V : Type*) (n : ℕ) where

The vertex sets of the n cliques.

A : Fin n → Finset V

Each clique has exactly n vertices.

card_eq : ∀ i, (A i).card = n

Two different cliques share at most one vertex, i.e. they are edge-disjoint.

inter_le : ∀ i j, i ≠ j → (A i ∩ A j).card ≤ 1

Every vertex lies in one of the cliques.

cover : ∀ v, ∃ i, v ∈ A inamespace EFLConfigvariable {V : Type*} {n : ℕ} (C : EFLConfig V n)

The union graph: distinct vertices are adjacent iff they lie in a common clique.

def graph : SimpleGraph V where Adj u v := u ≠ v ∧ ∃ i, u ∈ C.A i ∧ v ∈ C.A i symm := ⟨fun _ _ ⟨h, i, hu, hv⟩ => ⟨h.symm, i, hv, hu⟩⟩ loopless := ⟨fun _ h => h.1 rfl⟩

A vertex is shared if it lies in two different cliques.

def IsShared (v : V) : Prop := ∃ i j, i ≠ j ∧ v ∈ C.A i ∧ v ∈ C.A jopen scoped Classical in

The finite set of shared vertices.

noncomputable def sharedSet : Finset V := ((Finset.univ : Finset (Fin n)).biUnion C.A).filter C.IsShared

The graph $G$ contains a copy of $K_n$, so $n \le \chi(G)$.

V:Type u_1n:ℕC:EFLConfig V nhn:n > 0hcl:C.graph.IsClique ↑(C.A ⟨0, hn⟩)⊢ ↑n ≤ C.graph.chromaticNumber V:Type u_1n:ℕC:EFLConfig V nhn:n > 0hcl:C.graph.IsClique ↑(C.A ⟨0, hn⟩)this:↑(C.A ⟨0, hn⟩).card ≤ C.graph.chromaticNumber⊢ ↑n ≤ C.graph.chromaticNumber rwa [V:Type u_1n:ℕC:EFLConfig V nhn:n > 0hcl:C.graph.IsClique ↑(C.A ⟨0, hn⟩)this:↑n ≤ C.graph.chromaticNumber⊢ ↑n ≤ C.graph.chromaticNumberV:Type u_1n:ℕC:EFLConfig V nhn:n > 0hcl:C.graph.IsClique ↑(C.A ⟨0, hn⟩)this:↑n ≤ C.graph.chromaticNumber⊢ ↑n ≤ C.graph.chromaticNumber at this

A vertex that is not shared lies in exactly one clique.

@[category API, AMS 5] lemma eq_of_not_shared {v : V} (hv : ¬ C.IsShared v) {i j : Fin n} (hi : v ∈ C.A i) (hj : v ∈ C.A j) : i = j := V:Type u_1n:ℕC:EFLConfig V nv:Vhv:¬C.IsShared vi:Fin nj:Fin nhi:v ∈ C.A ihj:v ∈ C.A j⊢ i = j V:Type u_1n:ℕC:EFLConfig V nv:Vhv:¬C.IsShared vi:Fin nj:Fin nhi:v ∈ C.A ihj:v ∈ C.A jh:¬i = j⊢ False All goals completed! 🐙open scoped Classical in

If the shared vertices can be coloured with $n$ colours so that shared vertices in a common clique get distinct colours, then $G$ is $n$-colourable.

V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jsu:¬C.IsShared usv:¬C.IsShared vheq:↑((e j) ⟨u, ⋯⟩) = ↑((e j) ⟨v, ⋯⟩)⊢ False V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jsu:¬C.IsShared usv:¬C.IsShared vheq:↑((e j) ⟨u, ⋯⟩) = ↑((e j) ⟨v, ⋯⟩)this:⟨u, ⋯⟩ = ⟨v, ⋯⟩⊢ False All goals completed! 🐙open scoped Classical in

There are at most $\binom{n}{2}$ shared vertices, since two cliques share at most one vertex.

V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2 V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSetthis:C.sharedSet.card ≤ (Finset.powersetCard 2 Finset.univ).card⊢ C.sharedSet.card ≤ n.choose 2 All goals completed! 🐙end EFLConfigopen EFLConfig

If $G$ is an edge-disjoint union of $n$ copies of $K_n$, then is $\chi(G) = n$?

@[category research open, question, AMS 5] theorem erdos_19 : ∀ (V : Type) (n : ℕ) (C : EFLConfig V n), C.graph.chromaticNumber = n := ⊢ ∀ (V : Type) (n : ℕ) (C : EFLConfig V n), C.graph.chromaticNumber = ↑n All goals completed! 🐙open scoped Classical in

The Erdős–Faber–Lovász conjecture holds for $n \le 3$.

V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vhuv:c u = c vmu:u ∈ C.sharedSetmv:v ∈ C.sharedSet⊢ u = v V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vmu:u ∈ C.sharedSetmv:v ∈ C.sharedSethuv:Fin.castLE hS (C.sharedSet.equivFin ⟨u, mu⟩) = Fin.castLE hS (C.sharedSet.equivFin ⟨v, mv⟩)⊢ u = v V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vmu:u ∈ C.sharedSetmv:v ∈ C.sharedSethuv:Fin.castLE hS (C.sharedSet.equivFin ⟨u, mu⟩) = Fin.castLE hS (C.sharedSet.equivFin ⟨v, mv⟩)this:⟨u, mu⟩ = ⟨v, mv⟩⊢ u = v All goals completed! 🐙

Hindman [Hi81] proved the Erdős–Faber–Lovász conjecture for $n < 10$.

@[category research solved, AMS 5] theorem erdos_19.variants.lt_ten : ∀ (V : Type) (n : ℕ) (C : EFLConfig V n), n < 10 → C.graph.chromaticNumber = n := ⊢ ∀ (V : Type) (n : ℕ) (C : EFLConfig V n), n < 10 → C.graph.chromaticNumber = ↑n All goals completed! 🐙

Kahn [Ka92] proved that $\chi(G) \le (1 + o(1))n$.

@[category research solved, AMS 5] theorem erdos_19.variants.kahn : ∀ ε > (0 : ℝ), ∀ᶠ n in atTop, ∀ (V : Type) (C : EFLConfig V n), C.graph.Colorable ⌊(1 + ε) * n⌋₊ := ⊢ ∀ ε > 0, ∀ᶠ (n : ℕ) in atTop, ∀ (V : Type) (C : EFLConfig V n), C.graph.Colorable ⌊(1 + ε) * ↑n⌋₊ All goals completed! 🐙

Kang, Kelly, Kühn, Methuku and Osthus [KKKMO21] proved the Erdős–Faber–Lovász conjecture for all sufficiently large $n$.

@[category research solved, AMS 5] theorem erdos_19.variants.large_n : ∀ᶠ n in atTop, ∀ (V : Type) (C : EFLConfig V n), C.graph.chromaticNumber = n := ⊢ ∀ᶠ (n : ℕ) in atTop, ∀ (V : Type) (C : EFLConfig V n), C.graph.chromaticNumber = ↑n All goals completed! 🐙end Erdos19