ordered_ramsey_prop
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
- 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_numberThe 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…
- 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 β, 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'