ordered_ramsey_number
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
- 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_number_eq_of_prop_of_forall_lt_not_propAn ordered Ramsey number R_ord(H, H') is equal to N if the ordered Ramsey property holds at N and fails for all M < N.
- 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
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}