simple_graph_size_ramsey_le_of_arrows
Sanity: if G → (F, H) then r̂(F, H) ≤ e(G).
Statement
theorem simple_graph_size_ramsey_le_of_arrows {α β : Type*} (F : SimpleGraph α) (H : SimpleGraph β) (k : ℕ) (G : SimpleGraph (Fin k)) (hG : simple_graph_size_ramsey_arrows G F H) : simple_graph_size_ramsey F H ≤ G.edgeSet.ncard
- Source
- sanity lemma for simple_graph_size_ramsey
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_size_ramseyThe 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…
- 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 1
- 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).
The proof, explained
The size-Ramsey number r̂(F, H) is defined as the infimum of the edge counts of graphs on some vertex set Fin(k) that arrow the pair (F, H). Because G on Fin(k) arrows (F, H) by assumption, its edge count is an element of the set being minimized over. The result follows immediately since the infimum of a set of natural numbers is bounded above by any element of that set.
The size-Ramsey number r̂(F, H) is at most the number of edges in G.
By definition, the size-Ramsey number r̂(F, H) is the infimum of all edge counts of graphs on some Fin(k) that satisfy the arrowing property G → (F, H). The graph G on Fin(k) alongside the hypothesis hG witnesses that |E(G)| belongs to this set of candidate edge counts. Applying Nat.sInf_le yields that the infimum is at most |E(G)|.
uses
Nat.sInf_leNat.sInf_le ⟨k, G, rfl, hG⟩
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element in that set.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem simple_graph_size_ramsey_le_of_arrows {α β : Type*} (F : SimpleGraph α) (H : SimpleGraph β) (k : ℕ) (G : SimpleGraph (Fin k)) (hG : simple_graph_size_ramsey_arrows G F H) : simple_graph_size_ramsey F H ≤ G.edgeSet.ncard := Nat.sInf_le ⟨k, G, rfl, hG⟩