simple_graph_star_forest
def
The 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 other edges.
Statement
def simple_graph_star_forest (q : ℕ) (n : Fin q → ℕ) : SimpleGraph (Σ i : Fin q, Option (Fin (n i)))- Defined in
- arXiv:2610.25958 (Size Ramsey numbers of star forests with two components on one side), Section 1: the star forest ⊔_{i=1}^q K_{1,n_i}
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Used by 7
- 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_star_forest_not_adj_of_neSanity: vertices in different components of the star forest are not adjacent.
- 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).
- simple_graph_star_forest_adj_centre_leafSanity: in the star forest, the centre of component i is adjacent to each of its leaves.
- simple_graph_star_forest_adj_iffAdjacency in the star forest: same component, one vertex the centre and the other a leaf.
- 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_star_forest_edgeSet_ncardThe star forest K_{1,n_1} ⊔ ... ⊔ K_{1,n_q} has ∑ n_i edges.
Lean source view module on GitHub
def simple_graph_star_forest (q : ℕ) (n : Fin q → ℕ) : SimpleGraph (Σ i : Fin q, Option (Fin (n i))) where Adj u v := u.1 = v.1 ∧ ((u.2 = none ∧ v.2 ≠ none) ∨ (u.2 ≠ none ∧ v.2 = none)) symm := ⟨fun _ _ h => ⟨h.1.symm, h.2.symm.imp (fun h => ⟨h.2, h.1⟩) (fun h => ⟨h.2, h.1⟩)⟩⟩ loopless := ⟨fun _ h => by rcases h.2 with h | h · exact h.2 h.1 · exact h.1 h.2⟩