op_258_forces_two
For every decay profile a, a forces a monochromatic K_2.
Statement
theorem op_258_forces_two (a : ℕ+ → ℝ) : op_258_forces a 2- Source
- step towards op_258_triangle_forcing_implies_decay_ramsey
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- op_258_boundedA colouring c of the edges of the complete graph K_n is a-bounded if for every colour i the number of edges of colour i is at most a i *…
- 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…
- op_258_forcesThe decay profile a forces a monochromatic K_k if for all sufficiently large n, every a-bounded colouring of the edges of K_n has a…
- 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 states that any decay profile a forces a monochromatic K_2. Choosing the threshold n₀ = 2, every complete graph K_n on n ≥ 2 vertices contains two distinct vertices, 0 and 1, which span an edge e. The two-vertex set {0, 1} and the color c(e) immediately provide a monochromatic K_2, as this single edge is the only edge between the two vertices, rendering the decay bound hypothesis unnecessary.
To show that any decay profile a forces a monochromatic K_2, it suffices to show that every edge-colored complete graph on n ≥ 2 vertices contains a monochromatic K_2.
We choose the threshold n₀ = 2. For an arbitrary n ≥ 2, an edge-coloring c of K_n, and assuming the bound hypothesis, we unfold the definition of having a monochromatic clique of size 2: we must find a 2-element vertex set s and a color i such that all edges between distinct vertices in s have color i.
use 2 intro n hn c hc unfold op_258_has_mono_clique
The vertices v₀ = 0 and v₁ = 1 in Fin n are distinct and form an edge e in K_n.
Since n ≥ 2, both 0 < n and 1 < n hold by arithmetic, yielding two well-defined vertices v₀ and v₁ in Fin n. They are distinct because equality in Fin n implies equality of the underlying numbers via `Fin.mk.inj`, which would mean 0 = 1. Since v₀ ≠ v₁, the unordered pair s(v₀, v₁) is an edge e of the complete graph K_n.
uses
Fin.mk.injhave h0 : 0 < n := by omega have h1 : 1 < n := by omega let v0 : Fin n := ⟨0, h0⟩ let v1 : Fin n := ⟨1, h1⟩ have hne : v0 ≠ v1 := by intro h have := Fin.mk.inj h omega have he : s(v0, v1) ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet := by simp [hne] let e : (SimpleGraph.completeGraph (Fin n)).edgeSet := ⟨s(v0, v1), he⟩
The candidate set {v₀, v₁} has cardinality 2, and we select it along with color c(e).
We instantiate the existential witness with the vertex set s = {v₀, v₁} and the color i = c(e). Because v₀ ≠ v₁, the set has cardinality 2. It remains to verify that every edge spanned by this set has color c(e).
use {v0, v1}, c e refine ⟨by simp [hne], ?_⟩
Any two distinct vertices u, v ∈ {v₀, v₁} must be drawn from {v₀, v₁}, ruling out the case u = v = v₀.
Let u, v ∈ {v₀, v₁} with u ≠ v. Applying `Finset.mem_insert` and `Finset.mem_singleton`, each of u and v must be either v₀ or v₁. Splitting into cases, the diagonal possibility u = v₀ and v = v₀ contradicts u ≠ v.
uses
Finset.mem_insert,Finset.mem_singletonintro u v hu hv huv simp only [Finset.mem_insert, Finset.mem_singleton] at hu hv rcases hu with rfl | rfl <;> rcases hv with rfl | rfl · contradiction
When u = v₀ and v = v₁, the edge has color c(e).
The edge between v₀ and v₁ is definitionally identical to e as a subtype of unordered pairs via `Subtype.ext`. Rewriting with this equality shows that its color is c(e).
uses
Subtype.ext· have h_eq : (⟨s(v0, v1), by simp [huv]⟩ : (SimpleGraph.completeGraph (Fin n)).edgeSet) = e := by apply Subtype.ext rfl rw [h_eq]
When u = v₁ and v = v₀, the edge also has color c(e), and the diagonal case u = v = v₁ is contradictory.
By symmetry of unordered pairs (`Sym2.eq_swap`), s(v₁, v₀) = s(v₀, v₁), so by `Subtype.ext` the edge s(v₁, v₀) is equal to e and has color c(e). Finally, the case u = v₁ and v = v₁ is ruled out directly by u ≠ v.
uses
Subtype.ext,Sym2.eq_swap· have h_eq : (⟨s(v1, v0), by simp [huv]⟩ : (SimpleGraph.completeGraph (Fin n)).edgeSet) = e := by apply Subtype.ext exact Sym2.eq_swap rw [h_eq] · contradiction
Fin.mk.inj- If two elements of a finite type `Fin n` are equal, their underlying natural numbers are equal.
Finset.mem_insert- An element belongs to `insert b s` if and only if it equals `b` or belongs to `s`.
Finset.mem_singleton- An element belongs to the singleton `{a}` if and only if it equals `a`.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
Sym2.eq_swap- The unordered pair `s(a, b)` is equal to `s(b, a)`.
- The decay profile bound hypothesis (`op_258_bounded`) is completely unused because a single edge always forms a monochromatic $K_2$ regardless of the coloring.
- A substantial portion of the formal proof is administrative bookkeeping: checking subtype equality for edges and using symmetry of unordered pairs (`Sym2.eq_swap`) to show that the edge between $v_1$ and $v_0$ is the same as the edge between $v_0$ and $v_1$.
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.
/-- Sanity witness for the forcing predicate: every profile forces a monochromatic `K_2`, since two adjacent vertices always form one. The content of the target therefore starts at `k = 3`. -/theorem op_258_forces_two (a : ℕ+ → ℝ) : op_258_forces a 2 := by use 2 intro n hn c hc unfold op_258_has_mono_clique have h0 : 0 < n := by omega have h1 : 1 < n := by omega let v0 : Fin n := ⟨0, h0⟩ let v1 : Fin n := ⟨1, h1⟩ have hne : v0 ≠ v1 := by intro h have := Fin.mk.inj h omega have he : s(v0, v1) ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet := by simp [hne] let e : (SimpleGraph.completeGraph (Fin n)).edgeSet := ⟨s(v0, v1), he⟩ use {v0, v1}, c e refine ⟨by simp [hne], ?_⟩ intro u v hu hv huv simp only [Finset.mem_insert, Finset.mem_singleton] at hu hv rcases hu with rfl | rfl <;> rcases hv with rfl | rfl · contradiction · have h_eq : (⟨s(v0, v1), by simp [huv]⟩ : (SimpleGraph.completeGraph (Fin n)).edgeSet) = e := by apply Subtype.ext rfl rw [h_eq] · have h_eq : (⟨s(v1, v0), by simp [huv]⟩ : (SimpleGraph.completeGraph (Fin n)).edgeSet) = e := by apply Subtype.ext exact Sym2.eq_swap rw [h_eq] · contradiction