AFTD Auto-Formalizing Theoretical Domains

simple_graph_ramsey_property

def

simple_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 of H.

Statement

def simple_graph_ramsey_property {α β : Type*} (F : SimpleGraph α) (H : SimpleGraph β) (N : ℕ) : Prop
Defined in
arXiv:2610.36522
Verified
28 Oct 2026
Axioms
none listed
Used by 2
  • simple_graph_ramsey_numberThe 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.
  • simple_graph_ramsey_property_monoLet F and H be simple graphs. If the two-color Ramsey property holds on N vertices (every graph on N vertices contains F or its complement…

Read back from the Lean

For arbitrary types α and β, given a simple graph F on α, a simple graph H on β, and a natural number N, simple_graph_ramsey_property F H N asserts that: For every simple graph G on the vertex set Fin N (the set {0, 1, ..., N - 1}), at least one of the following holds: 1. F is contained in G (F.IsContained G), or 2. H is contained in the complement graph of G (H.IsContained Gᶜ). Here Gᶜ is the complement graph of G on Fin N, where distinct vertices u ≠ v are adjacent in Gᶜ if and only if they are not adjacent in 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 property for graphs F, H on N vertices. -/
def simple_graph_ramsey_property {α β : Type*} (F : SimpleGraph α) (H : SimpleGraph β) (N : ℕ) : Prop :=
  ∀ G : SimpleGraph (Fin N), F.IsContained G ∨ H.IsContained Gᶜ
See it in the graphDiscuss this resultChallenge it