op_258_no_mono_triangle_of_layering
If an edge colouring c of K_n is subordinate to a bipartite edge layering (so each colour lives in a layer whose endpoints have distinct values under a 2-colouring), then c contains no monochromatic triangle K_3.
Statement
theorem op_258_no_mono_triangle_of_layering (n : ℕ) (l : ℕ) (layer : (SimpleGraph.completeGraph (Fin n)).edgeSet → Fin l) (f : Fin l → Fin n → Fin 2) (h_bip : ∀ (u v : Fin n) (hne : u ≠ v), f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) u ≠ f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) v) (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) (col_layer : ℕ+ → Fin l) (hc_layer : ∀ e, col_layer (c e) = layer e) : ¬ op_258_has_mono_clique n c 3
- Source
- step towards op_258_sum_ne_top_of_forces_three
- Verified
- 22 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_sum_ne_top_of_forces_threeIf a positive antitone profile a forces a monochromatic triangle K_3 on sufficiently large complete graphs, then the infinite sum of a_i…
The proof, explained
The proof proceeds by contradiction. Suppose there exists a monochromatic triangle, that is, a 3-element set of vertices $s$ whose edges all have colour $i$. Since colour $i$ is subordinate to a single bipartite layer, every edge in the triangle connects vertices with different values under that layer's 2-colouring. This forces the 2-colouring function to be injective on the 3 vertices of $s$, implying $|s| \le 2$, which contradicts $|s| = 3$.
For any distinct vertices u and v, the unordered pair {u, v} is an edge of the complete graph K_n.
In the theorem signature, specifying the edge passed to `layer` in hypothesis `h_bip` requires proof that $s(u, v)$ belongs to the edge set of $K_n$. Simplifying with `SimpleGraph.completeGraph_eq_top` and the assumption $u \neq v$ discharges this requirement for both endpoints.
uses
SimpleGraph.completeGraph_eq_topf (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) u ≠ f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) v)
Suppose, for contradiction, that there is a monochromatic triangle: a set s of 3 vertices such that all edges between distinct vertices in s have the same colour i.
We assume for contradiction that `op_258_has_mono_clique n c 3` holds. Deconstructing this assumption gives a subset of vertices $s \subseteq \operatorname{Fin} n$ with $|s| = 3$ and a colour $i \in \mathbb{N}^+$ such that every edge between distinct vertices of $s$ has colour $i$.
rintro ⟨s, i, hcard, hmono⟩
For any two distinct vertices in s, their values under the 2-colouring of layer col_layer(i) must be distinct.
Let $u, v \in s$ be distinct vertices. By the monochromatic assumption, the edge between them has colour $i$. Since colour $i$ is assigned to layer $\operatorname{col\_layer}(i)$ (via hypothesis `hc_layer`), this edge belongs to that layer. The bipartiteness hypothesis `h_bip` states that any edge in a layer connects vertices with different 2-colouring values in that layer, so $f(\operatorname{col\_layer}(i))(u) \neq f(\operatorname{col\_layer}(i))(v)$.
uses
SimpleGraph.completeGraph_eq_tophave key : ∀ (u v : Fin n) (hu : u ∈ s) (hv : v ∈ s) (hne : u ≠ v), f (col_layer i) u ≠ f (col_layer i) v := by intro u v hu hv hne have hcv : c ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩ = i := hmono hu hv hne have hl : layer ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩ = col_layer i := by rw [← hc_layer ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩, hcv] simpa [hl] using h_bip u v hne
The restriction of the 2-colouring f(col_layer(i)) to s is an injective function from s to Fin 2.
If two vertices $x, y \in s$ had the same value under $f(\operatorname{col\_layer}(i))$, they could not be distinct by the previous claim (`key`), so $x = y$ (using `Subtype.ext` to lift the equality of underlying vertices).
uses
Subtype.exthave hinj : Function.Injective (fun x : s => f (col_layer i) (x : Fin n)) := by intro x y hxy by_contra hne exact key (x : Fin n) (y : Fin n) x.property y.property (fun h => hne (Subtype.ext h)) hxy
The cardinality of s is at most 2.
By `Fintype.card_le_of_injective`, the existence of an injective map from $s$ to $\operatorname{Fin} 2$ implies that $|s| \le |\operatorname{Fin} 2|$. Simplifying the cardinalities via `Fintype.card_coe` and `Fintype.card_fin` gives $|s| \le 2$.
uses
Fintype.card_le_of_injective,Fintype.card_coe,Fintype.card_finhave hle := Fintype.card_le_of_injective (fun x : s => f (col_layer i) (x : Fin n)) hinj simp only [Fintype.card_coe, Fintype.card_fin] at hle
False (a contradiction is derived).
Linear integer arithmetic (`omega`) detects the contradiction between the assumption $|s| = 3$ and the derived inequality $|s| \le 2$.
omega
SimpleGraph.completeGraph_eq_top- In a complete graph, every pair of distinct vertices forms an edge.
Subtype.ext- Two elements of a subtype are equal if and only if their underlying values are equal.
Fintype.card_le_of_injective- If an injective function exists between two finite types, the cardinality of the domain is at most the cardinality of the codomain.
Fintype.card_coe- The cardinality of a subtype induced by a finite set equals the cardinality of the finite set itself.
Fintype.card_fin- The cardinality of the standard finite type Fin n is n.
- Lines 6 and 7 are inline tactic proofs inside the theorem's hypotheses rather than the proof body: in Lean, an edge of a simple graph is represented as an unordered pair together with a membership proof, and `by simp [SimpleGraph.completeGraph_eq_top, hne]` discharges this obligation whenever $u \neq v$.
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.
/-- An edge colouring subordinate to a family of bipartite layers has no monochromatic K_3. -/theorem op_258_no_mono_triangle_of_layering (n : ℕ) (l : ℕ) (layer : (SimpleGraph.completeGraph (Fin n)).edgeSet → Fin l) (f : Fin l → Fin n → Fin 2) (h_bip : ∀ (u v : Fin n) (hne : u ≠ v), f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) u ≠ f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) v) (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) (col_layer : ℕ+ → Fin l) (hc_layer : ∀ e, col_layer (c e) = layer e) : ¬ op_258_has_mono_clique n c 3 := by rintro ⟨s, i, hcard, hmono⟩ have key : ∀ (u v : Fin n) (hu : u ∈ s) (hv : v ∈ s) (hne : u ≠ v), f (col_layer i) u ≠ f (col_layer i) v := by intro u v hu hv hne have hcv : c ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩ = i := hmono hu hv hne have hl : layer ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩ = col_layer i := by rw [← hc_layer ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩, hcv] simpa [hl] using h_bip u v hne have hinj : Function.Injective (fun x : s => f (col_layer i) (x : Fin n)) := by intro x y hxy by_contra hne exact key (x : Fin n) (y : Fin n) x.property y.property (fun h => hne (Subtype.ext h)) hxy have hle := Fintype.card_le_of_injective (fun x : s => f (col_layer i) (x : Fin n)) hinj simp only [Fintype.card_coe, Fintype.card_fin] at hle omega