AFTD Auto-Formalizing Theoretical Domains

cyclic_has_copy

def

A 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 to G preserving strict cyclic betweenness sbtw.

Statement

def cyclic_has_copy {m N : ℕ} (H : SimpleGraph (Fin m)) (G : SimpleGraph (Fin N)) : Prop
Defined in
arXiv:2611.08375, Sec. 1
Verified
06 Nov 2026
Axioms
none listed
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.
  • 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₂,…
  • 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, N$ and simple graphs $H$ on vertex set $\mathrm{Fin}(m)$ and $G$ on vertex set $\mathrm{Fin}(N)$, cyclic_has_copy H G asserts that there exists a function $f : \mathrm{Fin}(m) \to \mathrm{Fin}(N)$ such that: 1. $f$ is injective (Function.Injective f), 2. for all $u, v : \mathrm{Fin}(m)$, if $u$ and $v$ are adjacent in $H$, then $f(u)$ and $f(v)$ are adjacent in $G$ ($f$ is a graph homomorphism), and 3. for all $u, v, w : \mathrm{Fin}(m)$, if sbtw u v w holds (i.e., $u, v, w$ are in strict cyclic order / $v$ is strictly between $u$ and $w$ in the cyclic order on $\mathrm{Fin}(m)$), then sbtw (f u) (f v) (f w) holds on $\mathrm{Fin}(N)$ ($f$ preserves the strict betweenness / circular order relation).

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

/-- Existence of a cyclic order-preserving subgraph embedding. -/
def cyclic_has_copy {m N : ℕ} (H : SimpleGraph (Fin m)) (G : SimpleGraph (Fin N)) : Prop := ∃ f : Fin m → Fin N,
    Function.Injective f ∧
    (∀ ⦃u v : Fin m⦄, H.Adj u v → G.Adj (f u) (f v)) ∧
    (∀ ⦃u v w : Fin m⦄, sbtw u v w → sbtw (f u) (f v) (f w))
See it in the graphDiscuss this resultChallenge it