AFTD Auto-Formalizing Theoretical Domains

cyclic_ramsey_property

def

cyclic_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₂, represented by a graph G and its complement Gᶜ.

Statement

def cyclic_ramsey_property {m n : ℕ} (H₁ : SimpleGraph (Fin m)) (H₂ : SimpleGraph (Fin n)) (N : ℕ) : Prop
Defined in
arXiv:2611.08375, Sec. 1
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • cyclic_has_copyA cyclically ordered graph G on Fin N contains a cyclically ordered copy of H on Fin m if there is an injective graph homomorphism from H…
Used by 3
  • 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.
  • cyclic_ramsey_numberThe cyclic Ramsey number R_cyc(H₁, H₂) is the smallest positive integer N such that every 2-edge-colouring of the complete cyclically…

Read back from the Lean

Given natural numbers $m, n$, simple graphs $H_1$ on vertex set $\text{Fin } m$ and $H_2$ on vertex set $\text{Fin } n$, and a natural number $N$, cyclic_ramsey_property H₁ H₂ N is the proposition that for every simple graph $G$ on vertex set $\text{Fin } N$, either: 1. $G$ contains a cyclic copy of $H_1$ (there exists an injective map $f : \text{Fin } m \to \text{Fin } N$ that preserves adjacency from $H_1$ to $G$ and preserves the strict cyclic betweenness relation sbtw), or 2. The complement graph $G^c$ contains a cyclic copy of $H_2$ (there exists an injective map $f : \text{Fin } n \to \text{Fin } N$ that preserves adjacency from $H_2$ to $G^c$ and preserves 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 2-colour cyclic Ramsey property for graphs on cyclically ordered vertices. -/
def cyclic_ramsey_property {m n : ℕ} (H₁ : SimpleGraph (Fin m)) (H₂ : SimpleGraph (Fin n)) (N : ℕ) : Prop := ∀ G : SimpleGraph (Fin N), cyclic_has_copy H₁ G ∨ cyclic_has_copy H₂ Gᶜ
See it in the graphDiscuss this resultChallenge it