simple_graph_size_ramsey_star_star_forest
Lemma 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).
Statement
theorem simple_graph_size_ramsey_star_star_forest (p q : ℕ) (hp : 0 < p) (hq : 0 < q)
(n : Fin q → ℕ) (hn : ∀ i, 0 < n i) (hmono : Antitone n) :
simple_graph_size_ramsey (completeBipartiteGraph (Fin 1) (Fin p))
(simple_graph_star_forest q n) = ∑ i, (p + n i - 1)- Formalizes
- arXiv:2610.25958 (Size Ramsey numbers of star forests with two components on one side), Lemma 2.3
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- simple_graph_size_ramsey_star_star_forest_arrowsUpper bound of Lemma 2.3 of arXiv:2610.25958. Some finite graph with ∑_i (p + n_i - 1) edges arrows (K_{1,p}, ⊔_i K_{1,n_i}): the disjoint…
- simple_graph_size_ramsey_star_star_forest_edges_geLower bound of Lemma 2.3 of arXiv:2610.25958. Every finite graph G with G → (K_{1,p}, ⊔_i K_{1,n_i}) has at least ∑_i (p + n_i - 1) edges.
- simple_graph_size_ramsey_le_of_arrowsSanity: if G → (F, H) then r̂(F, H) ≤ e(G).
- 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_star_forestThe star forest K_{1,n_1} ⊔ ... ⊔ K_{1,n_q}: component i has a centre (i, none) adjacent to its n_i leaves (i, some j), and there are no…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - 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…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
The proof establishes the size Ramsey formula by proving matching upper and lower bounds. The upper bound is obtained by invoking an explicit construction of a graph with $\sum_{i=1}^q (p + n_i - 1)$ edges that arrows the pair $(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i})$. The lower bound follows from showing that any graph satisfying the arrowing relation must have at least that many edges, which establishes the candidate value as a lower bound on the infimum defining the size Ramsey number.
To establish the equality, it suffices to prove both $\hat{r}(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i}) \le \sum_{i=1}^q (p + n_i - 1)$ and $\sum_{i=1}^q (p + n_i - 1) \le \hat{r}(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i})$.
By antisymmetry of $\le$ on $\mathbb{N}$ (`le_antisymm`), equality between two numbers reduces to showing that each is less than or equal to the other.
uses
le_antisymmapply le_antisymm$\hat{r}(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i}) \le \sum_{i=1}^q (p + n_i - 1)$.
Lemma `simple_graph_size_ramsey_star_star_forest_arrows` provides an explicit graph $G$ with exactly $\sum_{i=1}^q (p + n_i - 1)$ edges that arrows $(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i})$. Since the size Ramsey number is defined as the infimum of the number of edges across all arrowing graphs, `simple_graph_size_ramsey_le_of_arrows` shows that the size Ramsey number is at most $|E(G)|$.
uses
simple_graph_size_ramsey_star_star_forest_arrows,simple_graph_size_ramsey_le_of_arrows· obtain ⟨k, G, hcard, hG⟩ := simple_graph_size_ramsey_star_star_forest_arrows p q hp n hn exact hcard ▸ simple_graph_size_ramsey_le_of_arrows _ _ k G hG
To prove $\sum_{i=1}^q (p + n_i - 1) \le \hat{r}(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i})$, it suffices to verify that the set of edge counts of graphs arrowing $(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i})$ is nonempty and that every element of that set is at least $\sum_{i=1}^q (p + n_i - 1)$.
The size Ramsey number $\hat{r}$ is defined as the infimum ($\mathrm{sInf}$) of the edge counts of graphs arrowing the two given graphs. By `le_csInf`, a candidate value is bounded above by the infimum of a set if the set is nonempty and the candidate value is a lower bound for every element of the set.
uses
le_csInf· apply le_csInfThe set of edge counts of graphs arrowing $(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i})$ is nonempty.
The graph $G$ supplied by `simple_graph_size_ramsey_star_star_forest_arrows` has $\sum_{i=1}^q (p + n_i - 1)$ edges and satisfies the arrowing relation, serving as an explicit witness that the set is nonempty.
uses
simple_graph_size_ramsey_star_star_forest_arrows· obtain ⟨k, G, hcard, hG⟩ := simple_graph_size_ramsey_star_star_forest_arrows p q hp n hn exact ⟨_, k, G, hcard, hG⟩
Every graph $G$ arrowing $(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i})$ has at least $\sum_{i=1}^q (p + n_i - 1)$ edges.
Let $m$ be an arbitrary element of the set, so $m = |E(G)|$ for some graph $G$ arrowing $(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i})$. Lemma `simple_graph_size_ramsey_star_star_forest_edges_ge` directly proves that $|E(G)| \ge \sum_{i=1}^q (p + n_i - 1)$.
uses
simple_graph_size_ramsey_star_star_forest_edges_ge· rintro m ⟨k, G, rfl, hG⟩ exact simple_graph_size_ramsey_star_star_forest_edges_ge p q hp n hn k G hG
le_antisymm- In a partial order, if $a \le b$ and $b \le a$, then $a = b$.
simple_graph_size_ramsey_star_star_forest_arrows- For positive $p$ and positive integers $n_i$, there exists a graph $G$ with $\sum_i (p + n_i - 1)$ edges such that $G$ arrows $(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i})$.
simple_graph_size_ramsey_le_of_arrows- If a graph $G$ arrows $(F, H)$, then the size Ramsey number $\hat{r}(F, H)$ is at most the number of edges of $G$.
le_csInf- In a conditionally complete lattice, a value $a$ is at most $\inf s$ provided $s$ is nonempty and $a \le b$ for all $b \in s$.
simple_graph_size_ramsey_star_star_forest_edges_ge- Any graph $G$ that arrows $(K_{1,p}, \bigsqcup_{i=1}^q K_{1, n_i})$ must have at least $\sum_i (p + n_i - 1)$ edges.
- Although the theorem statement assumes $0 < q$ (`hq`) and that $n$ is antitone (`hmono`) to match the formulation in Lemma 2.3 of arXiv:2610.25958, neither hypothesis is actually needed or used in the formal proof; the equality holds for any finite collection of stars with positive sizes.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem simple_graph_size_ramsey_star_star_forest (p q : ℕ) (hp : 0 < p) (hq : 0 < q) (n : Fin q → ℕ) (hn : ∀ i, 0 < n i) (hmono : Antitone n) : simple_graph_size_ramsey (completeBipartiteGraph (Fin 1) (Fin p)) (simple_graph_star_forest q n) = ∑ i, (p + n i - 1) := by apply le_antisymm · obtain ⟨k, G, hcard, hG⟩ := simple_graph_size_ramsey_star_star_forest_arrows p q hp n hn exact hcard ▸ simple_graph_size_ramsey_le_of_arrows _ _ k G hG · apply le_csInf · obtain ⟨k, G, hcard, hG⟩ := simple_graph_size_ramsey_star_star_forest_arrows p q hp n hn exact ⟨_, k, G, hcard, hG⟩ · rintro m ⟨k, G, rfl, hG⟩ exact simple_graph_size_ramsey_star_star_forest_edges_ge p q hp n hn k G hG