cyclic_ramsey_number
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}