AFTD Auto-Formalizing Theoretical Domains

weakened_cycle_ramsey_property

def

The weakened cycle Ramsey property weakened_cycle_ramsey_property t ℓ n holds if every t-edge-colouring of the complete graph K_n contains a cycle of length ℓ whose edges use at most t - 1 colours (that is, avoids at least one colour).

Statement

def weakened_cycle_ramsey_property (t ℓ n : ℕ) : Prop
Defined in
arXiv:2611.11187, Section 1 and Section 2.1
Verified
11 Nov 2026
Axioms
none listed
Built on 1
  • color_avoiding_subgraphFor a simple graph G and an edge colouring c with colours in C, the j-avoiding subgraph color_avoiding_subgraph G c j is the spanning…
Used by 2

Read back from the Lean

The definition weakened_cycle_ramsey_property t ℓ n asserts that: For all edge-colorings c of the complete graph on Fin n using t colors (i.e., functions c : (SimpleGraph.completeGraph (Fin n)).edgeSet → Fin t), there exists a color j : Fin t such that the cycle graph of length ℓ (SimpleGraph.cycleGraph ℓ) is contained (as a subgraph) in the color-avoiding subgraph of the complete graph on Fin n, which consists of all edges of the complete graph whose color under c is not j.

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

/-- Property that every t-edge-colouring of K_n contains a cycle of length ℓ avoiding some colour. -/
def weakened_cycle_ramsey_property (t ℓ n : ℕ) : Prop := ∀ c : (SimpleGraph.completeGraph (Fin n)).edgeSet → Fin t,
    ∃ j : Fin t, SimpleGraph.IsContained (SimpleGraph.cycleGraph ℓ) (color_avoiding_subgraph (SimpleGraph.completeGraph (Fin n)) c j)
See it in the graphDiscuss this resultChallenge it