AFTD Auto-Formalizing Theoretical Domains

ordered_ramsey_prop

def

For 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 copy of H or the complement Gᶜ contains an ordered copy of H'.

Statement

def ordered_ramsey_prop {α β : Type*} [LinearOrder α] [LinearOrder β]
    (H : SimpleGraph α) (H' : SimpleGraph β) (N : ℕ) : 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 1
  • has_ordered_copyAn 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…
Used by 4

Read back from the Lean

Given linearly ordered types α and β, simple graphs H on α and H' on β, and a natural number N, ordered_ramsey_prop H H' N asserts that for every simple graph G on the vertex set Fin N, at least one of the following holds: 1. There exists a strictly monotone map f : α → Fin N such that for all vertices u, v : α, if u and v are adjacent in H, then f u and f v are adjacent in G. 2. There exists a strictly monotone map f : β → Fin N such that for all vertices u, v : β, if u and v are adjacent in H', then f u and f v are adjacent in the graph complement 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

/-- Every 2-edge-colouring of the complete ordered graph on N vertices contains a red copy of H or a blue copy of H'. -/
def ordered_ramsey_prop {α β : Type*} [LinearOrder α] [LinearOrder β]
    (H : SimpleGraph α) (H' : SimpleGraph β) (N : ℕ) : Prop := ∀ G : SimpleGraph (Fin N), has_ordered_copy G H ∨ has_ordered_copy Gᶜ H'
See it in the graphDiscuss this resultChallenge it