AFTD Auto-Formalizing Theoretical Domains

op_258_mono_clique_of_fiber_gt_turan

theoremverified

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.

  1. 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.

    lines 7–11

      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⟩
  2. 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.

    lines 12–25

    uses Sym2.ind, SimpleGraph.mem_edgeSet, SimpleGraph.top_adj, Sym2.mk_isDiag_iff, Finset.coe_image, Set.mem_compl_iff, Sym2.mem_diagSet

      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
  3. 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.

    lines 26–33

    uses SimpleGraph.edgeSet_fromEdgeSet, Set.mem_sdiff

      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⟩
  4. 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.

    lines 34–53

    uses SimpleGraph.isClique_iff, SimpleGraph.mem_edgeSet, Finset.mem_coe, Finset.mem_image, Finset.mem_filter, Subtype.ext

      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 _
  5. 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.

    lines 54–56

    uses SimpleGraph.CliqueFree.card_edgeFinset_le, Fintype.card_fin, SimpleGraph.edgeFinset, Set.toFinset_card, Nat.card_eq_fintype_card

      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
  6. 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|.

    lines 57–59

    uses Nat.card_congr, Equiv.setCongr, Nat.card_coe_set_eq, Set.ncard_coe_finset, Finset.card_image_of_injective, Subtype.ext

      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)
  7. 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.

    lines 60–61

      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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it