AFTD Auto-Formalizing Theoretical Domains

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 4

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)
See it in the graphDiscuss this resultChallenge it