simple_graph_size_ramsey_star_star_forest_arrows
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
- simple_graph_star_forest_edgeSet_ncardThe star forest K_{1,n_1} ⊔ ... ⊔ K_{1,n_q} has ∑ n_i edges.
- complete_bipartite_one_isContained_of_adjA vertex v with p distinct neighbours g(0), ..., g(p-1) in R gives a copy of the star K_{1,p} in R.
- 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…
- 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
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.
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.
uses
SimpleGraph.edgeSet_map,Set.ncard_image_of_injective,simple_graph_star_forest_edgeSet_ncardclassical 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
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.
uses
SimpleGraph.map_adj,Equiv.coe_toEmbedding,EmbeddingLike.apply_eq_iff_eqintro 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⟩
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.
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_univlet 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
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.
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
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.
uses
Fin.castLE_injective,Finset.mem_filter,Finset.mem_univ,true_andlet 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
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}.
uses
SimpleGraph.sdiff_adj,Option.ne_none_iff_exists'.mp,Or.inl,Or.inr,Sigma.mk.inj_iff,heq_eq_eq,Option.map_injectivelet ψ : (Σ 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.
- On line 52, `omega` closes the inequality `n i ≤ (blue i).card` using linear integer arithmetic from `red i + blue i = p + n i - 1`, `red i < p`, and `0 < n i`.
- The vertices of a star forest are formally represented as dependent pairs `⟨i, x⟩` with `i : Fin q` and `x : Option (Fin m_i)`, where `none` represents the center of the `i`-th star and `some j` represents the `j`-th leaf. This structure is relabeled to `Fin k` via an explicit finite equivalence `e`.
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_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