has_ordered_copy
def
An ordered graph G contains an ordered copy of an ordered graph H if there exists a strictly monotone map f from the vertex set of H to that of G such that every edge of H maps to an edge of G.
Statement
def has_ordered_copy {α β : Type*} [LinearOrder α] [LinearOrder β] (G : SimpleGraph β) (H : SimpleGraph α) : Prop
- Defined in
- arXiv:2611.08375 "New results on cyclic and ordered Ramsey numbers", Section 1
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 4
- ordered_ramsey_monotone_cycle_alternating_path_twoFor all integers k ≥ 3, the ordered Ramsey number of the monotone cycle MC_k and the alternating path AP_2 is equal to k.
- ordered_ramsey_propFor ordered graphs H and H' and natural number N, ordered_ramsey_prop H H' N holds if for every graph G on Fin N, G contains an ordered…
- has_ordered_copy_selfEvery ordered graph contains an ordered copy of itself via the identity map.
- ordered_ramsey_monotone_cycle_three_alternating_path_threeThe ordered Ramsey number of the monotone cycle MC_3 and the alternating path AP_3 is equal to 5.
Read back from the Lean
For linearly ordered types α and β, a simple graph G on β, and a simple graph H on α, has_ordered_copy G H asserts that there exists a function f : α → β such that f is strictly monotone (for all u, v : α with u < v, f(u) < f(v)) and for all u, v : α, if u and v are adjacent in H, then f(u) and f(v) are adjacent in G.
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
/-- An ordered graph G contains an ordered copy of H if there is an order-preserving edge-preserving map from V(H) to V(G). -/ def has_ordered_copy {α β : Type*} [LinearOrder α] [LinearOrder β] (G : SimpleGraph β) (H : SimpleGraph α) : Prop := ∃ f : α → β, StrictMono f ∧ ∀ ⦃u v : α⦄, H.Adj u v → G.Adj (f u) (f v)