AFTD Auto-Formalizing Theoretical Domains

ordered_ramsey_number

def

The ordered Ramsey number R_ord(H, H') of ordered graphs H and H' is the infimum of natural numbers N such that every 2-edge-colouring of the complete ordered graph on N vertices contains an ordered copy of H in the first colour or H' in the second colour.

Statement

noncomputable def ordered_ramsey_number {α β : Type*} [LinearOrder α] [LinearOrder β]
    (H : SimpleGraph α) (H' : SimpleGraph β) : ℕ
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
  • 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…
Used by 3

Read back from the Lean

Given linearly ordered types α and β and simple graphs H on α and H' on β, ordered_ramsey_number H H' is defined as the infimum (in ℕ) of the set of natural numbers N such that for every simple graph G on the vertex set Fin N, either G contains an ordered copy of H or the graph complement Gᶜ contains an ordered copy of H' (where an ordered copy is a strictly monotonic map on vertices that preserves adjacency).

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

/-- The ordered Ramsey number R_ord(H, H') is the minimum N such that every 2-edge-colouring of K_N ordered contains H in the first colour or H' in the second colour. -/
noncomputable def ordered_ramsey_number {α β : Type*} [LinearOrder α] [LinearOrder β]
    (H : SimpleGraph α) (H' : SimpleGraph β) : ℕ := sInf {N : ℕ | ordered_ramsey_prop H H' N}
See it in the graphDiscuss this resultChallenge it