AFTD Auto-Formalizing Theoretical Domains

simple_graph_size_ramsey

def

The size Ramsey number r̂(F, H) = min{e(G) : G → (F, H)} over finite graphs G, taken here as graphs on Fin k; every finite graph is isomorphic to one of these. It is 0 if no such G exists.

Statement

noncomputable def simple_graph_size_ramsey {α β : Type*} (F : SimpleGraph α)
    (H : SimpleGraph β) : ℕ
Defined in
arXiv:2610.25958 (Size Ramsey numbers of star forests with two components on one side), Section 1: definition of the size Ramsey number
Verified
23 Oct 2026
Axioms
none listed
Built on 1
  • simple_graph_size_ramsey_arrowsG → (F, H): every red/blue colouring of the edges of G has a red copy of F or a blue copy of H. The red edges form a subgraph R ≤ G and…
Used by 2

Lean source view module on GitHub

noncomputable def simple_graph_size_ramsey {α β : Type*} (F : SimpleGraph α)
    (H : SimpleGraph β) : ℕ :=
  sInf {m | ∃ (k : ℕ) (G : SimpleGraph (Fin k)), G.edgeSet.ncard = m ∧
    simple_graph_size_ramsey_arrows G F H}
See it in the graphDiscuss this resultChallenge it