AFTD Auto-Formalizing Theoretical Domains

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}
See it in the graphDiscuss this resultChallenge it