AFTD Auto-Formalizing Theoretical Domains

decay_ramsey_arrow_mono

theoremverified

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.

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

    line 7

    uses SimpleGraph.completeGraph_eq_top

              c ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i) :
  2. 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.

    line 12

    uses SimpleGraph.completeGraph_eq_top

              c ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i := by
  3. 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.

    lines 13–14

      obtain ⟨n₀, hn₀⟩ := h
      refine ⟨n₀, fun n hn c hc => ?_⟩
  4. 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.

    line 15

      obtain ⟨s, i, hcard, hcol⟩ := hn₀ n hn c hc
  5. There 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.

    lines 16–17

    uses Finset.exists_subset_card_eq

      have hk_le : k ≤ s.card := by omega
      obtain ⟨t, hts, htcard⟩ := Finset.exists_subset_card_eq hk_le
  6. 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.

    line 18

      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.

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

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