op_258_mono_clique_of_fiber_gt_turan
If a single colour class of an edge colouring of K_n has strictly more edges than the Turán bound for K_{r+1}-free graphs (r ≥ 1), then the colouring has a monochromatic K_{r+1} in that colour.
Statement
theorem op_258_mono_clique_of_fiber_gt_turan (n r : ℕ) (hr : 1 ≤ r) (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) (i : ℕ+) (h : (Finset.univ.filter (fun e => c e = i)).card > (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2) : op_258_has_mono_clique n c (r + 1)
- Source
- step towards op_258_forces_step
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- op_258_has_mono_cliqueThe colouring c of the edges of K_n has a monochromatic K_k: there are a k-element vertex set s and a colour i such that every edge inside…
- Used by 1
- op_258_forces_of_capacity_lt_oneIf k ≥ 2 and Σ_i min(a_i, 1 - 1/(k-1)) < 1, then every a-bounded colouring of K_n for large n already contains a monochromatic K_k; i.e. a…
The proof, explained
The theorem is proved by contradiction using Turán's theorem. Given an edge colouring of the complete graph K_n in which the set F of edges of colour i has strictly more edges than the Turán bound for K_{r+1}-free graphs, we construct the subgraph G on n vertices whose edges are precisely those of colour i. If the colouring contained no monochromatic clique of size r + 1 in colour i, then G would be K_{r+1}-free and would therefore have at most as many edges as the Turán bound. But G has exactly |F| edges, contradicting the hypothesis.
Define the subgraph G on Fin n whose edges are the pairs assigned colour i.
We work classically. We define F as the finset of edges of the complete graph K_n having colour i, and S as the set of their underlying unordered pairs in Sym²(Fin n). We then let G be the simple graph on Fin n induced by the edge set S.
classical set F : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet := Finset.univ.filter (fun e => c e = i) with hF set S : Finset (Sym2 (Fin n)) := F.image (fun e : (SimpleGraph.completeGraph (Fin n)).edgeSet => (e : Sym2 (Fin n))) with hS obtain ⟨G, hG⟩ : ∃ G : SimpleGraph (Fin n), G = SimpleGraph.fromEdgeSet (S : Set (Sym2 (Fin n))) := ⟨_, rfl⟩
No pair in S is a self-loop (diagonal), so S ⊆ (Sym2.diagSet)ᶜ.
Every edge in the complete graph connects two distinct vertices a ≠ b, so its unordered pair cannot be diagonal. Since every element of S is the underlying pair of an edge of K_n, no element of S is on the diagonal.
uses
Sym2.ind,SimpleGraph.mem_edgeSet,SimpleGraph.top_adj,Sym2.mk_isDiag_iff,Finset.coe_image,Set.mem_compl_iff,Sym2.mem_diagSethave hsub : (S : Set (Sym2 (Fin n))) ⊆ Sym2.diagSetᶜ := by have aux : ∀ z : Sym2 (Fin n), z ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet → ¬ z.IsDiag := by intro z hz induction z using Sym2.ind with | _ a b => rw [SimpleGraph.mem_edgeSet] at hz rw [SimpleGraph.top_adj] at hz rw [Sym2.mk_isDiag_iff] exact hz intro x hx rw [hS, Finset.coe_image] at hx obtain ⟨e, _, rfl⟩ := hx rw [Set.mem_compl_iff, Sym2.mem_diagSet] exact aux _ e.2
The edge set of G is exactly S.
By definition, `SimpleGraph.fromEdgeSet S` forms a graph whose edge set is S \ Sym2.diagSet. Because S contains no diagonal elements by the previous step, removing the diagonal leaves S unchanged, so G.edgeSet = S.
uses
SimpleGraph.edgeSet_fromEdgeSet,Set.mem_sdiffhave hGedge : G.edgeSet = (S : Set (Sym2 (Fin n))) := by rw [hG, SimpleGraph.edgeSet_fromEdgeSet] ext x simp only [Set.mem_sdiff] constructor · rintro ⟨h1, _⟩; exact h1 · intro h1 exact ⟨h1, by have := hsub h1; simpa using this⟩
Assuming there is no monochromatic K_{r+1} in colour i, the graph G contains no clique of size r + 1.
We argue by contradiction and assume there is no monochromatic (r+1)-clique. If G had a clique t of size r + 1, then all pairs of distinct vertices u, v ∈ t would be adjacent in G, so their edge s(u, v) would belong to G.edgeSet = S. Every such edge in S originates from an edge of K_n coloured i, so t would span a monochromatic (r+1)-clique of colour i, contradicting our assumption. Hence G is (r+1)-clique-free.
uses
SimpleGraph.isClique_iff,SimpleGraph.mem_edgeSet,Finset.mem_coe,Finset.mem_image,Finset.mem_filter,Subtype.extby_contra hn have hGcf : G.CliqueFree (r + 1) := by intro t ht apply hn refine ⟨t, i, ht.card_eq, ?_⟩ intro u v hu hv huv have hpw : (↑t : Set (Fin n)).Pairwise G.Adj := (SimpleGraph.isClique_iff G).mp ht.isClique have hadj : G.Adj u v := hpw hu hv huv have hmem : Sym2.mk u v ∈ G.edgeSet := (SimpleGraph.mem_edgeSet G).mpr hadj rw [hGedge] at hmem rw [hS, Finset.mem_coe, Finset.mem_image] at hmem obtain ⟨e, heF, hev⟩ := hmem have heF' : c e = i := by rw [hF, Finset.mem_filter] at heF exact heF.2 have key : ∀ (hh : Sym2.mk u v ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet), c ⟨Sym2.mk u v, hh⟩ = i := by intro hh have hx : (⟨Sym2.mk u v, hh⟩ : (SimpleGraph.completeGraph (Fin n)).edgeSet) = e := Subtype.ext hev.symm rw [hx]; exact heF' exact key _
The number of edges of G is at most the Turán bound for K_{r+1}-free graphs on n vertices.
By Turán's theorem (`SimpleGraph.CliqueFree.card_edgeFinset_le`), any (r+1)-clique-free graph on n vertices has at most (n² - (n % r)²)(r - 1) / (2r) + choose (n % r) 2 edges. We then rewrite the edge finset cardinality in terms of the general cardinality `Nat.card` of the edge set.
uses
SimpleGraph.CliqueFree.card_edgeFinset_le,Fintype.card_fin,SimpleGraph.edgeFinset,Set.toFinset_card,Nat.card_eq_fintype_cardhave hbound := SimpleGraph.CliqueFree.card_edgeFinset_le (V := Fin n) (G := G) (r := r) hGcf simp only [Fintype.card_fin] at hbound rw [SimpleGraph.edgeFinset, Set.toFinset_card, ← Nat.card_eq_fintype_card] at hbound
The number of edges of G equals the number of edges of colour i, |E(G)| = |F|.
The edge set of G is S, which is the image of F under the canonical inclusion of edges of K_n into Sym²(Fin n). Because this inclusion map on subtypes is injective, |S| = |F|.
uses
Nat.card_congr,Equiv.setCongr,Nat.card_coe_set_eq,Set.ncard_coe_finset,Finset.card_image_of_injective,Subtype.exthave hNat : Nat.card ↥G.edgeSet = F.card := by rw [Nat.card_congr (Equiv.setCongr hGedge), Nat.card_coe_set_eq, Set.ncard_coe_finset, hS] exact Finset.card_image_of_injective _ (fun a b hab => Subtype.ext hab)
Contradiction between the Turán bound and the assumed size of colour class i.
Substituting |E(G)| = |F| into the Turán upper bound gives that |F| is at most the Turán bound. Linear integer arithmetic (`omega`) detects the contradiction with the hypothesis that |F| strictly exceeds this bound.
rw [hNat] at hbound omega
Finset.card_image_of_injective- The image of a finset under an injective function has the same cardinality as the original finset.
Finset.coe_image- The coercion of the image of a finset under a function equals the set-theoretic image of the coerced finset.
Finset.mem_coe- An element belongs to the set coercion of a finset if and only if it belongs to the finset.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_image- An element b belongs to the image of a finset under f if and only if b = f(a) for some element a in the finset.
Fintype.card_fin- The cardinality of the finite type Fin n is n.
Equiv.setCongr- Two sets that are equal have canonically equivalent subtypes.
Nat.card_congr- Equivalent types (in bijection) have the same cardinality.
Nat.card_eq_fintype_card- For a finite type, its cardinality as a natural number (Nat.card) equals its Fintype cardinality.
Nat.card_coe_set_eq- The natural cardinality of the subtype of a set s equals the set cardinality (ncard) of s.
Set.mem_compl_iff- An element belongs to the complement of a set if and only if it does not belong to the set.
Set.mem_sdiff- An element belongs to the set difference s \ t if and only if it belongs to s and not to t.
Set.ncard_coe_finset- The set cardinality (ncard) of the set coercion of a finset s equals the finset cardinality of s.
Set.toFinset_card- The cardinality of a finite set converted to a finset equals the Fintype cardinality of its subtype.
SimpleGraph.CliqueFree.card_edgeFinset_le- Turán's theorem: any graph on a finite vertex set V that is K_{r+1}-free has at most (|V|² - (|V| % r)²)(r - 1) / (2r) + choose (|V| % r) 2 edges.
SimpleGraph.edgeFinset- The edge finset of a graph with a finite edge set is defined as the edge set converted to a finset.
SimpleGraph.edgeSet_fromEdgeSet- The edge set of a simple graph formed from a set of pairs s consists of all non-diagonal pairs in s (s \ diagSet).
SimpleGraph.isClique_iff- A set of vertices is a clique in G if and only if every pair of distinct vertices in the set is adjacent in G.
SimpleGraph.mem_edgeSet- An unordered pair s(v, w) belongs to the edge set of G if and only if v and w are adjacent in G.
SimpleGraph.top_adj- In the complete graph, two vertices are adjacent if and only if they are distinct.
Subtype.ext- Two elements of a subtype are equal if and only if their underlying values are equal.
Sym2.ind- Induction principle for unordered pairs: a property holds for all unordered pairs if it holds for pairs of the form s(x, y).
Sym2.mem_diagSet- An unordered pair belongs to the diagonal set if and only if it is a diagonal pair (a self-loop s(x, x)).
Sym2.mk_isDiag_iff- An unordered pair s(x, y) is on the diagonal if and only if x = y.
- The formal proof devotes lines 12–33 to proving that the edge set of the constructed graph G is strictly equal to S: in Mathlib, `SimpleGraph.fromEdgeSet` deletes diagonal pairs (self-loops) by definition, so the proof must explicitly verify that edges of K_n connect distinct vertices.
- Lines 56–59 bridge several distinct cardinality notions in Mathlib (`Fintype.card`, `Nat.card`, `Set.ncard`, and `Finset.card`) to transfer the Turán bound on G's edge set to the cardinality of the finset F.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A colour class larger than the Turán bound forces a monochromatic clique in that colour. -/theorem op_258_mono_clique_of_fiber_gt_turan (n r : ℕ) (hr : 1 ≤ r) (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) (i : ℕ+) (h : (Finset.univ.filter (fun e => c e = i)).card > (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2) : op_258_has_mono_clique n c (r + 1) := by classical set F : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet := Finset.univ.filter (fun e => c e = i) with hF set S : Finset (Sym2 (Fin n)) := F.image (fun e : (SimpleGraph.completeGraph (Fin n)).edgeSet => (e : Sym2 (Fin n))) with hS obtain ⟨G, hG⟩ : ∃ G : SimpleGraph (Fin n), G = SimpleGraph.fromEdgeSet (S : Set (Sym2 (Fin n))) := ⟨_, rfl⟩ have hsub : (S : Set (Sym2 (Fin n))) ⊆ Sym2.diagSetᶜ := by have aux : ∀ z : Sym2 (Fin n), z ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet → ¬ z.IsDiag := by intro z hz induction z using Sym2.ind with | _ a b => rw [SimpleGraph.mem_edgeSet] at hz rw [SimpleGraph.top_adj] at hz rw [Sym2.mk_isDiag_iff] exact hz intro x hx rw [hS, Finset.coe_image] at hx obtain ⟨e, _, rfl⟩ := hx rw [Set.mem_compl_iff, Sym2.mem_diagSet] exact aux _ e.2 have hGedge : G.edgeSet = (S : Set (Sym2 (Fin n))) := by rw [hG, SimpleGraph.edgeSet_fromEdgeSet] ext x simp only [Set.mem_sdiff] constructor · rintro ⟨h1, _⟩; exact h1 · intro h1 exact ⟨h1, by have := hsub h1; simpa using this⟩ by_contra hn have hGcf : G.CliqueFree (r + 1) := by intro t ht apply hn refine ⟨t, i, ht.card_eq, ?_⟩ intro u v hu hv huv have hpw : (↑t : Set (Fin n)).Pairwise G.Adj := (SimpleGraph.isClique_iff G).mp ht.isClique have hadj : G.Adj u v := hpw hu hv huv have hmem : Sym2.mk u v ∈ G.edgeSet := (SimpleGraph.mem_edgeSet G).mpr hadj rw [hGedge] at hmem rw [hS, Finset.mem_coe, Finset.mem_image] at hmem obtain ⟨e, heF, hev⟩ := hmem have heF' : c e = i := by rw [hF, Finset.mem_filter] at heF exact heF.2 have key : ∀ (hh : Sym2.mk u v ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet), c ⟨Sym2.mk u v, hh⟩ = i := by intro hh have hx : (⟨Sym2.mk u v, hh⟩ : (SimpleGraph.completeGraph (Fin n)).edgeSet) = e := Subtype.ext hev.symm rw [hx]; exact heF' exact key _ have hbound := SimpleGraph.CliqueFree.card_edgeFinset_le (V := Fin n) (G := G) (r := r) hGcf simp only [Fintype.card_fin] at hbound rw [SimpleGraph.edgeFinset, Set.toFinset_card, ← Nat.card_eq_fintype_card] at hbound have hNat : Nat.card ↥G.edgeSet = F.card := by rw [Nat.card_congr (Equiv.setCongr hGedge), Nat.card_coe_set_eq, Set.ncard_coe_finset, hS] exact Finset.card_image_of_injective _ (fun a b hab => Subtype.ext hab) rw [hNat] at hbound omega