AFTD Auto-Formalizing Theoretical Domains

decay_ramsey_arrow

def

For 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 each colour i has at most a i * choose(n, 2) edges contains a monochromatic clique K_k.

Statement

def decay_ramsey_arrow (a : ℕ+ → ℝ) (k : ℕ) : Prop
Defined in
arXiv:2610.20577, Section 1
Verified
18 Oct 2026
Axioms
none listed
Used by 1
  • decay_ramsey_not_arrow_of_powersIf 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…

Read back from the Lean

decay_ramsey_arrow a k asserts that there exists a threshold natural number n₀ such that for every natural number n ≥ n₀, and for every coloring c : (completeGraph (Fin n)).edgeSet → ℕ+ of the edges of the complete graph on n vertices by positive integers: if for every color i : ℕ+, the number of edges colored i is at most a(i) * (n.choose 2) (as real numbers), then there exist a vertex subset s ⊆ Fin n of size k and a color i : ℕ+ such that every pair of distinct vertices u, v ∈ s is connected by an edge colored i (that is, s forms a monochromatic clique of size k in color i).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The arrow relation a → K_k: every a-bounded edge-colouring of large complete graphs contains a monochromatic K_k. -/
def decay_ramsey_arrow (a : ℕ+ → ℝ) (k : ℕ) : Prop := ∃ 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
See it in the graphDiscuss this resultChallenge it