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
- simple_graph_size_ramsey_le_of_arrowsSanity: if G → (F, H) then r̂(F, H) ≤ e(G).
- simple_graph_size_ramsey_star_star_forestLemma 2.3 of arXiv:2610.25958: for positive integers p, q, n_1 ≥ ... ≥ n_q, r̂(K_{1,p}, ⊔_{i=1}^q K_{1,n_i}) = ∑_{i=1}^q (p + n_i - 1).
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}