AFTD Auto-Formalizing Theoretical Domains

simple_graph_size_ramsey_star_star_forest

theoremverifiedformalization

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

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.

  1. 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.

    line 5

    uses le_antisymm

      apply le_antisymm
  2. $\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)|$.

    lines 6–7

    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
  3. 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.

    line 8

    uses le_csInf

      · apply le_csInf
  4. The 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.

    lines 9–10

    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⟩
  5. 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)$.

    lines 11–12

    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.

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

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
See it in the graphDiscuss this resultChallenge it