AFTD Auto-Formalizing Theoretical Domains

simple_graph_size_ramsey_star_star_forest_arrows

theoremverified

Upper 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 union of the stars K_{1,p+n_i-1}.

Statement

theorem simple_graph_size_ramsey_star_star_forest_arrows (p q : ℕ) (hp : 0 < p) (n : Fin q → ℕ)
    (hn : ∀ i, 0 < n i) :
    ∃ (k : ℕ) (G : SimpleGraph (Fin k)), G.edgeSet.ncard = ∑ i, (p + n i - 1) ∧
      simple_graph_size_ramsey_arrows G (completeBipartiteGraph (Fin 1) (Fin p))
        (simple_graph_star_forest q n)
Source
upper bound in the proof of arXiv:2610.25958 (Size Ramsey numbers of star forests with two components on one side), Lemma 2.3 (PR-280)
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1

The proof, explained

To show that some graph with ∑_i (p + n_i - 1) edges arrows (K_{1,p}, ⨆_i K_{1,n_i}), the proof constructs G as the disjoint union of q stars with star sizes m_i = p + n_i - 1, which has precisely the required edge count. For any 2-coloring of the edges of G into red (subgraph R) and blue (subgraph G \ R), each star center has m_i incident edges. If some star center has at least p incident red edges, these edges span a monochromatic red K_{1,p} inside R. Otherwise, every star center has at most p - 1 red edges, leaving at least m_i - (p - 1) = n_i blue edges at each center i, which together embed the target star forest ⨆_i K_{1,n_i} into the blue subgraph G \ R.

  1. The candidate graph G is defined as the disjoint union of stars K_{1, m_i} with m_i = p + n_i - 1 on vertex set Fin k, and has exactly ∑_i (p + n_i - 1) edges.

    For each index i, we set the star size m_i = p + n_i - 1. We consider the star forest S = ⨆_i K_{1, m_i} on the vertex type Σ_i Option (Fin (m_i)), and transport it along a bijection e to Fin k to obtain G. Because e is injective, the number of edges of G equals the number of edges of S, which is ∑_i m_i = ∑_i (p + n_i - 1) by simple_graph_star_forest_edgeSet_ncard.

    lines 6–12

    uses SimpleGraph.edgeSet_map, Set.ncard_image_of_injective, simple_graph_star_forest_edgeSet_ncard

      classical
      let m : Fin q → ℕ := fun i => p + n i - 1
      let e := Fintype.equivFin (Σ i : Fin q, Option (Fin (m i)))
      let S := simple_graph_star_forest q m
      refine ⟨_, S.map e.toEmbedding, ?_, ?_⟩
      · rw [SimpleGraph.edgeSet_map, Set.ncard_image_of_injective _ e.toEmbedding.sym2Map.injective]
        exact simple_graph_star_forest_edgeSet_ncard q m
  2. Two vertices e(a) and e(b) are adjacent in G if and only if a and b are adjacent in S.

    Fix an arbitrary subgraph R ≤ G, representing the red edges in a 2-coloring. Since G is the pushforward of S along the bijection e, adjacency in G is equivalent to adjacency in S.

    lines 13–23

    uses SimpleGraph.map_adj, Equiv.coe_toEmbedding, EmbeddingLike.apply_eq_iff_eq

      intro R _
      have hGadj : ∀ a b, (S.map e.toEmbedding).Adj (e a) (e b) ↔ S.Adj a b := by
        intro a b
        rw [SimpleGraph.map_adj]
        constructor
        · rintro ⟨a', b', h, ha, hb⟩
          simp only [Equiv.coe_toEmbedding, EmbeddingLike.apply_eq_iff_eq] at ha hb
          subst ha hb
          exact h
        · intro h
          exact ⟨a, b, h, rfl, rfl⟩
  3. If some star center has at least p incident red edges, then R contains a copy of K_{1,p}.

    For each star i, let red(i) be the set of leaves adjacent to the center e⟨i, none⟩ in R. We split cases on whether there is some star i with |red(i)| ≥ p. If so, we select p leaves from red(i) via the order embedding of Fin p into red(i). Since these p vertices are distinct and each is connected to the center in R, complete_bipartite_one_isContained_of_adj provides an embedding of K_{1,p} into R.

    lines 24–37

    uses complete_bipartite_one_isContained_of_adj, Sigma.mk.inj_iff, heq_eq_eq, true_and, Option.some.injEq, Fin.castLE_injective, Finset.mem_filter, Finset.mem_univ

      let red : ∀ i, Finset (Fin (m i)) := fun i =>
        Finset.univ.filter (fun j => R.Adj (e ⟨i, none⟩) (e ⟨i, some j⟩))
      by_cases hc : ∃ i, p ≤ (red i).card
      · obtain ⟨i, hi⟩ := hc
        left
        refine complete_bipartite_one_isContained_of_adj R p (e ⟨i, none⟩)
          (fun j => e ⟨i, some ((red i).orderEmbOfFin rfl (Fin.castLE hi j))⟩) ?_ (fun j => ?_)
        · intro a b h
          have h := e.injective h
          simp only [Sigma.mk.inj_iff, heq_eq_eq, true_and, Option.some.injEq] at h
          exact Fin.castLE_injective hi (((red i).orderEmbOfFin rfl).injective h)
        · have := (red i).orderEmbOfFin_mem rfl (Fin.castLE hi j)
          simp only [red, Finset.mem_filter, Finset.mem_univ, true_and] at this
          exact this
  4. If every star center has strictly fewer than p incident red edges, then each star center has at least n_i incident blue edges.

    In the remaining case, |red(i)| < p for all i. Defining blue(i) as the non-red leaves of star i, the partition identity |red(i)| + |blue(i)| = m_i = p + n_i - 1 combined with |red(i)| ≤ p - 1 and n_i > 0 guarantees |blue(i)| ≥ n_i, verified by omega.

    lines 38–52

    uses Finset.card_filter_add_card_filter_not, Finset.card_univ, Fintype.card_fin

      · push Not at hc
        right
        let blue : ∀ i, Finset (Fin (m i)) := fun i =>
          Finset.univ.filter (fun j => ¬ R.Adj (e ⟨i, none⟩) (e ⟨i, some j⟩))
        have hb : ∀ i, n i ≤ (blue i).card := by
          intro i
          have h1 := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin (m i))))
            (fun j => R.Adj (e ⟨i, none⟩) (e ⟨i, some j⟩))
          rw [Finset.card_univ, Fintype.card_fin] at h1
          have h2 := hc i
          have h3 := hn i
          have h4 : m i = p + n i - 1 := rfl
          simp only [red] at h2
          simp only [blue]
          omega
  5. For each star i, there is an injective map from Fin (n_i) to Fin (m_i) picking n_i distinct blue leaves.

    Using |blue(i)| ≥ n_i, we define b_i : Fin (n_i) → Fin (m_i) by taking the first n_i elements of blue(i) via Fin.castLE. This map is injective, and each leaf b_i(j) is not adjacent to the center in R, meaning the edge belongs to the blue subgraph G \ R.

    lines 53–60

    uses Fin.castLE_injective, Finset.mem_filter, Finset.mem_univ, true_and

        let b : ∀ i, Fin (n i) → Fin (m i) := fun i j => (blue i).orderEmbOfFin rfl (Fin.castLE (hb i) j)
        have hbinj : ∀ i, Function.Injective (b i) := fun i =>
          ((blue i).orderEmbOfFin rfl).injective.comp (Fin.castLE_injective (hb i))
        have hbmem : ∀ i j, ¬ R.Adj (e ⟨i, none⟩) (e ⟨i, some (b i j)⟩) := by
          intro i j
          have := (blue i).orderEmbOfFin_mem rfl (Fin.castLE (hb i) j)
          simp only [blue, Finset.mem_filter, Finset.mem_univ, true_and] at this
          exact this
  6. The target star forest ⨆_i K_{1, n_i} embeds into the blue subgraph G \ R.

    We construct a map ψ sending the center ⟨i, none⟩ to e⟨i, none⟩ and the leaf ⟨i, some j⟩ to e⟨i, some (b_i(j))⟩. Any edge in the star forest connects a center to a leaf within the same component i, and its image is an edge of G that is not in R, hence an edge of G \ R. Injectivity of ψ follows from the injectivity of e and of each b_i. Thus G \ R contains ⨆_i K_{1, n_i}.

    lines 61–83

    uses SimpleGraph.sdiff_adj, Option.ne_none_iff_exists'.mp, Or.inl, Or.inr, Sigma.mk.inj_iff, heq_eq_eq, Option.map_injective

        let ψ : (Σ i : Fin q, Option (Fin (n i))) → Fin (Fintype.card (Σ i : Fin q, Option (Fin (m i)))) :=
          fun x => e ⟨x.1, x.2.map (b x.1)⟩
        refine ⟨⟨⟨ψ, ?_⟩, ?_⟩⟩
        · rintro ⟨i, a⟩ ⟨i', c⟩ ⟨hii, h⟩
          simp only at hii
          subst hii
          rw [SimpleGraph.sdiff_adj]
          rcases h with ⟨ha, hc'⟩ | ⟨ha, hc'⟩
          · simp only at ha hc'
            subst ha
            obtain ⟨c, rfl⟩ := Option.ne_none_iff_exists'.mp hc'
            exact ⟨(hGadj _ _).2 ⟨rfl, Or.inl ⟨rfl, by simp⟩⟩, hbmem i c⟩
          · simp only at ha hc'
            subst hc'
            obtain ⟨a, rfl⟩ := Option.ne_none_iff_exists'.mp ha
            exact ⟨(hGadj _ _).2 ⟨rfl, Or.inr ⟨by simp, rfl⟩⟩, fun h => hbmem i a h.symm⟩
        · rintro ⟨i, a⟩ ⟨i', c⟩ h
          have h := e.injective h
          simp only [Sigma.mk.inj_iff] at h ⊢
          obtain ⟨rfl, h⟩ := h
          refine ⟨rfl, ?_⟩
          rw [heq_eq_eq] at h ⊢
          exact Option.map_injective (hbinj i) h
SimpleGraph.edgeSet_map
The edge set of a graph mapped along an injective vertex embedding is the image of the original edge set under the embedding lifted to unordered pairs.
Set.ncard_image_of_injective
An injective map preserves the set cardinality of the image of any set.
simple_graph_star_forest_edgeSet_ncard
The number of edges in a disjoint union of stars with leaf counts n_i is ∑_i n_i.
SimpleGraph.map_adj
Two vertices in the mapped graph are adjacent if and only if they are the images of adjacent vertices in the original graph.
Equiv.coe_toEmbedding
The coercion of an equivalence to an embedding equals the underlying function of the equivalence.
EmbeddingLike.apply_eq_iff_eq
Applying an embedding to two elements gives equal values if and only if the elements themselves are equal.
complete_bipartite_one_isContained_of_adj
A graph contains the star K_{1,p} as a subgraph if there is a vertex adjacent to p distinct vertices.
Sigma.mk.inj_iff
Two dependent pairs ⟨a₁, b₁⟩ and ⟨a₂, b₂⟩ are equal if and only if a₁ = a₂ and b₁ equals b₂.
heq_eq_eq
Heterogeneous equality between two elements of the same type is equivalent to standard equality.
true_and
The conjunction True ∧ P simplifies to P.
Option.some.injEq
Two optional values some x and some y are equal if and only if x = y.
Fin.castLE_injective
The canonical inclusion map from Fin m into Fin n for m ≤ n is injective.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the finset and satisfies the filtering predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.card_filter_add_card_filter_not
For any finset s and predicate p, the count of elements satisfying p plus the count of elements not satisfying p equals the cardinality of s.
Finset.card_univ
The cardinality of the universal finset on a finite type equals the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
SimpleGraph.sdiff_adj
An edge belongs to the graph difference G \ R if and only if it belongs to G and does not belong to R.
Option.ne_none_iff_exists'.mp
An optional value is not none if and only if it is some x for some x.
Or.inl
If A holds, then A ∨ B holds.
Or.inr
If B holds, then A ∨ B holds.
Option.map_injective
Applying Option.map to an injective function yields an injective function on optional values.

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_arrows (p q : ℕ) (hp : 0 < p) (n : Fin q → ℕ)    (hn : ∀ i, 0 < n i) :    ∃ (k : ℕ) (G : SimpleGraph (Fin k)), G.edgeSet.ncard = ∑ i, (p + n i - 1) ∧      simple_graph_size_ramsey_arrows G (completeBipartiteGraph (Fin 1) (Fin p))        (simple_graph_star_forest q n) := by  classical  let m : Fin q → ℕ := fun i => p + n i - 1  let e := Fintype.equivFin (Σ i : Fin q, Option (Fin (m i)))  let S := simple_graph_star_forest q m  refine ⟨_, S.map e.toEmbedding, ?_, ?_⟩  · rw [SimpleGraph.edgeSet_map, Set.ncard_image_of_injective _ e.toEmbedding.sym2Map.injective]    exact simple_graph_star_forest_edgeSet_ncard q m  intro R _  have hGadj : ∀ a b, (S.map e.toEmbedding).Adj (e a) (e b) ↔ S.Adj a b := by    intro a b    rw [SimpleGraph.map_adj]    constructor    · rintro ⟨a', b', h, ha, hb⟩      simp only [Equiv.coe_toEmbedding, EmbeddingLike.apply_eq_iff_eq] at ha hb      subst ha hb      exact h    · intro h      exact ⟨a, b, h, rfl, rfl⟩  let red : ∀ i, Finset (Fin (m i)) := fun i =>    Finset.univ.filter (fun j => R.Adj (e ⟨i, none⟩) (e ⟨i, some j⟩))  by_cases hc : ∃ i, p ≤ (red i).card  · obtain ⟨i, hi⟩ := hc    left    refine complete_bipartite_one_isContained_of_adj R p (e ⟨i, none⟩)      (fun j => e ⟨i, some ((red i).orderEmbOfFin rfl (Fin.castLE hi j))⟩) ?_ (fun j => ?_)    · intro a b h      have h := e.injective h      simp only [Sigma.mk.inj_iff, heq_eq_eq, true_and, Option.some.injEq] at h      exact Fin.castLE_injective hi (((red i).orderEmbOfFin rfl).injective h)    · have := (red i).orderEmbOfFin_mem rfl (Fin.castLE hi j)      simp only [red, Finset.mem_filter, Finset.mem_univ, true_and] at this      exact this  · push Not at hc    right    let blue : ∀ i, Finset (Fin (m i)) := fun i =>      Finset.univ.filter (fun j => ¬ R.Adj (e ⟨i, none⟩) (e ⟨i, some j⟩))    have hb : ∀ i, n i ≤ (blue i).card := by      intro i      have h1 := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin (m i))))        (fun j => R.Adj (e ⟨i, none⟩) (e ⟨i, some j⟩))      rw [Finset.card_univ, Fintype.card_fin] at h1      have h2 := hc i      have h3 := hn i      have h4 : m i = p + n i - 1 := rfl      simp only [red] at h2      simp only [blue]      omega    let b : ∀ i, Fin (n i) → Fin (m i) := fun i j => (blue i).orderEmbOfFin rfl (Fin.castLE (hb i) j)    have hbinj : ∀ i, Function.Injective (b i) := fun i =>      ((blue i).orderEmbOfFin rfl).injective.comp (Fin.castLE_injective (hb i))    have hbmem : ∀ i j, ¬ R.Adj (e ⟨i, none⟩) (e ⟨i, some (b i j)⟩) := by      intro i j      have := (blue i).orderEmbOfFin_mem rfl (Fin.castLE (hb i) j)      simp only [blue, Finset.mem_filter, Finset.mem_univ, true_and] at this      exact this    let ψ : (Σ i : Fin q, Option (Fin (n i))) → Fin (Fintype.card (Σ i : Fin q, Option (Fin (m i)))) :=      fun x => e ⟨x.1, x.2.map (b x.1)⟩    refine ⟨⟨⟨ψ, ?_⟩, ?_⟩⟩    · rintro ⟨i, a⟩ ⟨i', c⟩ ⟨hii, h⟩      simp only at hii      subst hii      rw [SimpleGraph.sdiff_adj]      rcases h with ⟨ha, hc'⟩ | ⟨ha, hc'⟩      · simp only at ha hc'        subst ha        obtain ⟨c, rfl⟩ := Option.ne_none_iff_exists'.mp hc'        exact ⟨(hGadj _ _).2 ⟨rfl, Or.inl ⟨rfl, by simp⟩⟩, hbmem i c⟩      · simp only at ha hc'        subst hc'        obtain ⟨a, rfl⟩ := Option.ne_none_iff_exists'.mp ha        exact ⟨(hGadj _ _).2 ⟨rfl, Or.inr ⟨by simp, rfl⟩⟩, fun h => hbmem i a h.symm⟩    · rintro ⟨i, a⟩ ⟨i', c⟩ h      have h := e.injective h      simp only [Sigma.mk.inj_iff] at h ⊢      obtain ⟨rfl, h⟩ := h      refine ⟨rfl, ?_⟩      rw [heq_eq_eq] at h ⊢      exact Option.map_injective (hbinj i) h
See it in the graphDiscuss this resultChallenge it