cyclic_has_copy
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))