decay_ramsey_arrow_mono
For every sequence a : ℕ+ → ℝ and integer k ≥ 2, if every a-bounded colouring of sufficiently large complete graphs contains a monochromatic K_{k+1}, then every a-bounded colouring contains a monochromatic K_k.
Statement
theorem decay_ramsey_arrow_mono (a : ℕ+ → ℝ) (k : ℕ) (hk : 2 ≤ k) (h : ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+, (∀ i : ℕ+, ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card ≤ a i * (n.choose 2 : ℝ)) → ∃ (s : Finset (Fin n)) (i : ℕ+), s.card = k + 1 ∧ ∀ ⦃u v : Fin n⦄, u ∈ s → v ∈ s → (h : u ≠ v) → c ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i) : ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+, (∀ i : ℕ+, ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card ≤ a i * (n.choose 2 : ℝ)) → ∃ (s : Finset (Fin n)) (i : ℕ+), s.card = k ∧ ∀ ⦃u v : Fin n⦄, u ∈ s → v ∈ s → (h : u ≠ v) → c ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i
- Source
- arXiv:2610.20577, Section 1
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
Given a function $a : \mathbb{N}^+ \to \mathbb{R}$, a natural number $k$, and an assumption that $2 \le k$, if there exists $n_0 \in \mathbb{N}$ such that for all $n \ge n_0$ and every edge-coloring $c : E(K_n) \to \mathbb{N}^+$ of the complete graph on vertex set $\operatorname{Fin} n$, the condition that every color $i \in \mathbb{N}^+$ appears on at most $a(i) \binom{n}{2}$ edges implies the existence of a monochromatic clique of size $k + 1$ (i.e., a subset $s \subseteq \operatorname{Fin} n$ with $|s| = k + 1$ and a color $i \in \mathbb{N}^+$ such that every pair of distinct vertices $u, v \in s$ has $c(\{u, v\}) = i$), then there exists $n_0 \in \mathbb{N}$ such that for all $n \ge n_0$ and every edge-coloring $c : E(K_n) \to \mathbb{N}^+$ satisfying the same upper bound on the number of edges of each color, there exists a monochromatic clique of size $k$ in some color $i \in \mathbb{N}^+$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes that forcing a monochromatic K_{k+1} implies forcing a monochromatic K_k under the same threshold n₀. Given an a-bounded colouring of a complete graph on n ≥ n₀ vertices, the hypothesis provides a monochromatic clique s of size k + 1. Since k ≤ k + 1, selecting any k-element subset t ⊆ s yields a monochromatic clique of size k.
Any two distinct vertices u ≠ v form an edge in the complete graph (in the hypothesis).
In the definition of the hypothesis h, each edge is a subtype packaging an unordered pair of vertices with a proof of adjacency. For the complete graph, SimpleGraph.completeGraph_eq_top simplifies adjacency to u ≠ v, which is discharged by the local hypothesis h : u ≠ v.
uses
SimpleGraph.completeGraph_eq_topc ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i) :
Any two distinct vertices u ≠ v form an edge in the complete graph (in the goal).
Similarly, in the conclusion of the theorem, the edge membership condition for distinct vertices u ≠ v is proved by simplifying with SimpleGraph.completeGraph_eq_top.
uses
SimpleGraph.completeGraph_eq_topc ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i := by
It suffices to show that for every n ≥ n₀ and every a-bounded colouring c, there exists a monochromatic K_k.
We unpack the assumed hypothesis h to obtain the threshold n₀. We choose this exact n₀ as the threshold for the conclusion, and let n ≥ n₀ and an a-bounded colouring c be given.
obtain ⟨n₀, hn₀⟩ := h refine ⟨n₀, fun n hn c hc => ?_⟩
There exists a monochromatic clique s of size k + 1 in some color i.
Applying the hypothesis hn₀ to n ≥ n₀ and the colouring c yields a vertex subset s of size k + 1 and a color i such that all edges between distinct vertices in s have color i.
obtain ⟨s, i, hcard, hcol⟩ := hn₀ n hn c hcThere exists a subset t ⊆ s of cardinality k.
Since |s| = k + 1, we have k ≤ |s| by linear arithmetic (closed by omega). Applying Finset.exists_subset_card_eq then provides a subset t ⊆ s of size k.
uses
Finset.exists_subset_card_eqhave hk_le : k ≤ s.card := by omega obtain ⟨t, hts, htcard⟩ := Finset.exists_subset_card_eq hk_le
The subset t is a monochromatic clique of size k with color i, completing the proof.
The subset t has cardinality k. Furthermore, since t ⊆ s, any two distinct vertices u, v ∈ t also belong to s, so their connecting edge has color i by the monochromaticity of s.
exact ⟨t, i, htcard, fun u v hut hvt huv => hcol (hts hut) (hts hvt) huv⟩
SimpleGraph.completeGraph_eq_top- The complete graph on a vertex type V is the top element of the simple graph lattice, so any two distinct vertices are connected by an edge.
Finset.exists_subset_card_eq- Any finite set with at least n elements contains a subset of cardinality n.
- Lines 7 and 12 contain inline tactic proofs (`by simp [SimpleGraph.completeGraph_eq_top, h]`) within the theorem statement. In Lean, an edge of the complete graph is represented as an unordered pair together with a proof of adjacency; the tactic simp discharges this proof using the fact that u ≠ 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.
/-- Monotonicity of the arrow relation: forcing K_{k+1} implies forcing K_k. -/theorem decay_ramsey_arrow_mono (a : ℕ+ → ℝ) (k : ℕ) (hk : 2 ≤ k) (h : ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+, (∀ i : ℕ+, ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card ≤ a i * (n.choose 2 : ℝ)) → ∃ (s : Finset (Fin n)) (i : ℕ+), s.card = k + 1 ∧ ∀ ⦃u v : Fin n⦄, u ∈ s → v ∈ s → (h : u ≠ v) → c ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i) : ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+, (∀ i : ℕ+, ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card ≤ a i * (n.choose 2 : ℝ)) → ∃ (s : Finset (Fin n)) (i : ℕ+), s.card = k ∧ ∀ ⦃u v : Fin n⦄, u ∈ s → v ∈ s → (h : u ≠ v) → c ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i := by obtain ⟨n₀, hn₀⟩ := h refine ⟨n₀, fun n hn c hc => ?_⟩ obtain ⟨s, i, hcard, hcol⟩ := hn₀ n hn c hc have hk_le : k ≤ s.card := by omega obtain ⟨t, hts, htcard⟩ := Finset.exists_subset_card_eq hk_le exact ⟨t, i, htcard, fun u v hut hvt huv => hcol (hts hut) (hts hvt) huv⟩