AFTD Auto-Formalizing Theoretical Domains

decay_ramsey_not_arrow_of_powers

theoremverified

If m ≥ 2 and for every integer ℓ ≥ 1 the complete graph K_{m^ℓ} admits an a-bounded edge-colouring with no monochromatic K_k, then the sequence a does not force K_k (that is, ¬ (a → K_k)).

Statement

theorem decay_ramsey_not_arrow_of_powers (m : ℕ) (hm : 2 ≤ m) (k : ℕ) (a : ℕ+ → ℝ)
    (h_pow : ∀ ℓ : ℕ, 1 ≤ ℓ → ∃ c : (SimpleGraph.completeGraph (Fin (m ^ ℓ))).edgeSet → ℕ+,
      op_258_bounded a (m ^ ℓ) c ∧ ¬ op_258_has_mono_clique (m ^ ℓ) c k) :
    ¬ decay_ramsey_arrow a k
Source
arXiv:2610.20577, Lemma 5.1
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • decay_ramsey_arrowFor a sequence a : ℕ+ → ℝ and integer k, decay_ramsey_arrow a k holds if for all sufficiently large n, every edge-colouring of K_n where…
  • 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 *…

Read back from the Lean

Let $m, k \in \mathbb{N}$ with $m \ge 2$, and let $a : \mathbb{N}^+ \to \mathbb{R}$. Suppose that for every natural number $\ell \ge 1$, there exists an edge-coloring $c : E(K_{m^\ell}) \to \mathbb{N}^+$ of the complete graph on $m^\ell$ vertices such that: 1. $c$ is bounded by $a$ (op_258_bounded a (m ^ ℓ) c), meaning for each color $i \in \mathbb{N}^+$, at most $a(i) \binom{m^\ell}{2}$ edges receive color $i$; and 2. $c$ contains no monochromatic clique of size $k$ (¬ op_258_has_mono_clique (m ^ ℓ) c k). Then decay_ramsey_arrow a k is false, meaning there does not exist any threshold $n_0 \in \mathbb{N}$ such that for all $n \ge n_0$, every edge-coloring of $K_n$ by $\mathbb{N}^+$ satisfying the bounds given by $a$ must contain a monochromatic clique of size $k$.

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 proceeds by contradiction: assuming that the sequence a forces K_k, there must be a threshold n₀ such that every a-bounded colouring of K_n for n ≥ n₀ contains a monochromatic K_k. Evaluating the power hypothesis at ℓ = n₀ + 1 produces an a-bounded colouring of K_{m^{n₀+1}} without any monochromatic K_k. But since m ≥ 2, we have m^{n₀+1} > n₀ + 1 ≥ n₀, so the threshold property applies to this colouring and forces a monochromatic K_k, yielding a contradiction.

  1. Assume for contradiction that the sequence a forces K_k, providing a threshold n₀.

    We assume decay_ramsey_arrow a k for contradiction. By definition, this yields a threshold n₀ ∈ ℕ such that every a-bounded edge-colouring of K_n with n ≥ n₀ contains a monochromatic K_k.

    line 6

      intro ⟨n₀, hn₀⟩
  2. There exists an a-bounded colouring c of K_{m^{n₀+1}} with no monochromatic K_k.

    Since 1 ≤ n₀ + 1 by Nat.le_add_left, we can instantiate the hypothesis h_pow with ℓ = n₀ + 1. This provides an edge-colouring c of the complete graph on m^{n₀+1} vertices that is a-bounded and has no monochromatic clique of size k.

    lines 7–8

    uses Nat.le_add_left

      have hℓ : 1 ≤ n₀ + 1 := Nat.le_add_left 1 n₀
      obtain ⟨c, hc_bounded, hc_not_mono⟩ := h_pow (n₀ + 1) hℓ
  3. n₀ ≤ m^{n₀+1}.

    Since m ≥ 2, we have m > 1. By Nat.lt_pow_self, n₀ + 1 < m^{n₀+1}. Linear integer arithmetic (omega) then implies n₀ ≤ m^{n₀+1}.

    lines 9–12

    uses Nat.lt_pow_self

      have hm1 : 1 < m := hm
      have h_le : n₀ ≤ m ^ (n₀ + 1) := by
        have := Nat.lt_pow_self hm1 (n := n₀ + 1)
        omega
  4. A contradiction is obtained.

    Because m^{n₀+1} ≥ n₀, the threshold hypothesis hn₀ applies to the graph K_{m^{n₀+1}} and colouring c, asserting the existence of a monochromatic K_k. This directly contradicts the construction of c having no monochromatic K_k.

    line 13

      exact hc_not_mono (hn₀ (m ^ (n₀ + 1)) h_le c hc_bounded)
Nat.le_add_left
For any natural numbers n and m, n ≤ m + n.
Nat.lt_pow_self
For any base a > 1 and exponent n, n < a ^ 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

/-- If K_{m^ℓ} admits an a-bounded K_k-free colouring for all ℓ ≥ 1 where m ≥ 2, then a does not force K_k. -/theorem decay_ramsey_not_arrow_of_powers (m : ℕ) (hm : 2 ≤ m) (k : ℕ) (a : ℕ+ → ℝ)    (h_pow : ∀ ℓ : ℕ, 1 ≤ ℓ → ∃ c : (SimpleGraph.completeGraph (Fin (m ^ ℓ))).edgeSet → ℕ+,      op_258_bounded a (m ^ ℓ) c ∧ ¬ op_258_has_mono_clique (m ^ ℓ) c k) :    ¬ decay_ramsey_arrow a k := by  intro ⟨n₀, hn₀⟩  have hℓ : 1 ≤ n₀ + 1 := Nat.le_add_left 1 n₀  obtain ⟨c, hc_bounded, hc_not_mono⟩ := h_pow (n₀ + 1) hℓ  have hm1 : 1 < m := hm  have h_le : n₀ ≤ m ^ (n₀ + 1) := by    have := Nat.lt_pow_self hm1 (n := n₀ + 1)    omega  exact hc_not_mono (hn₀ (m ^ (n₀ + 1)) h_le c hc_bounded)
See it in the graphDiscuss this resultChallenge it