AFTD Auto-Formalizing Theoretical Domains

cyclic_ramsey_number

def

The cyclic Ramsey number R_cyc(H₁, H₂) is the smallest positive integer N such that every 2-edge-colouring of the complete cyclically ordered graph on N vertices contains a monochromatic cyclic copy of H₁ or H₂.

Statement

noncomputable def cyclic_ramsey_number {m n : ℕ} (H₁ : SimpleGraph (Fin m)) (H₂ : SimpleGraph (Fin n)) : ℕ
Defined in
arXiv:2611.08375, Sec. 1
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • cyclic_ramsey_propertycyclic_ramsey_property H₁ H₂ N holds if every red/blue edge-colouring of K_N contains a red cyclic copy of H₁ or a blue cyclic copy of H₂,…
Used by 2
  • op_1258_cyclic_ramsey_k2_l3The cyclic Ramsey number R_cyc(NM_4, MP_3) of the 2-edge nested matching NM_4 and the monotone path MP_3 is equal to 4.
  • op_1258_cyclic_ramsey_k_oneFor every integer l ≥ 3, the cyclic Ramsey number R_cyc(NM_2, MP_l) of the 1-edge nested matching and the monotone path MP_l equals l.

Read back from the Lean

Given natural numbers m and n (implicit) and simple graphs H₁ on Fin m and H₂ on Fin n, cyclic_ramsey_number H₁ H₂ is defined as the infimum (in ℕ) of the set of positive natural numbers N such that every simple graph G on Fin N has the property that either G contains a copy of H₁ or the complement graph Gᶜ contains a copy of H₂, where a "copy" means an injective vertex map that preserves graph adjacency and preserves the strict cyclic betweenness relation (sbtw).

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 cyclic Ramsey number of two cyclically ordered graphs. -/
noncomputable def cyclic_ramsey_number {m n : ℕ} (H₁ : SimpleGraph (Fin m)) (H₂ : SimpleGraph (Fin n)) : ℕ := sInf {N : ℕ | 0 < N ∧ cyclic_ramsey_property H₁ H₂ N}
See it in the graphDiscuss this resultChallenge it