simple_graph_ramsey_number
def
The Ramsey number R(F, H) is the smallest positive integer N such that every graph on N vertices contains F or its complement contains H.
Statement
noncomputable def simple_graph_ramsey_number {α β : Type*} (F : SimpleGraph α) (H : SimpleGraph β) : ℕ
- Defined in
- arXiv:2610.36522
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Built on 1
- simple_graph_ramsey_propertysimple_graph_ramsey_property F H N holds if every simple graph G on N vertices contains a copy of F or its complement Gᶜ contains a copy…
Read back from the Lean
Given types α and β and simple graphs F : SimpleGraph α and H : SimpleGraph β, simple_graph_ramsey_number F H is defined as the infimum (sInf) in ℕ of the set of all positive natural numbers N (0 < N) such that for every simple graph G on the vertex set Fin N, either F is contained in G (F.IsContained G) or H is contained in the complement graph Gᶜ (H.IsContained 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
/-- The 2-color Ramsey number R(F, H) of two simple graphs F and H. -/ noncomputable def simple_graph_ramsey_number {α β : Type*} (F : SimpleGraph α) (H : SimpleGraph β) : ℕ := sInf {N : ℕ | 0 < N ∧ simple_graph_ramsey_property F H N}