star_graph_zero_forcing_poly_unimodal
For every natural number n, the complete bipartite graph K_{1, n} on Unit ⊕ Fin n has a unimodal zero forcing polynomial.
Statement
theorem star_graph_zero_forcing_poly_unimodal (n : ℕ) :
polynomial_is_unimodal (zero_forcing_poly (completeBipartiteGraph Unit (Fin n)))- Formalizes
- arXiv:2611.11352 Sec. 1
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- zero_forcing_polyGiven a finite type V and a simple graph G on V, zero_forcing_poly G is the polynomial in Polynomial ℕ defined as the sum over all subsets…
- polynomial_is_unimodalA polynomial with natural coefficients is unimodal if its coefficient sequence is weakly increasing up to some index and weakly decreasing…
- tree_zero_forcing_poly_lower_half_monotoneFor any finite tree $T$ on a finite vertex set $V$, the coefficient of $X^i$ in the zero forcing polynomial of $T$ is less than or equal…
- ZeroForcedThe zero forcing closure of an initial set S of blue vertices in G under the color change rule.
- is_zero_forcing_setA set of vertices S is a zero forcing set of G if its zero forcing closure contains all vertices of G.
Read back from the Lean
For every natural number $n$, the zero forcing polynomial of the star graph (the complete bipartite graph with parts Unit and Fin n, i.e., $K_{1, n}$) is unimodal.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The zero forcing polynomial of the star graph K_{1, n} has coefficients counting the zero forcing sets of each size. For n ≥ 1, any zero forcing set must contain at least n - 1 vertices, so all coefficients below n - 1 vanish, and no subset can exceed n + 1 vertices. Monotonicity below the peak at n follows because the only nonzero coefficients are at n - 1 and n, with an injection from size n - 1 to size n given by adjoining the center vertex; above the peak, the coefficient at n + 1 is at most 1 while the coefficient at n is at least 1.
If a set S misses two distinct leaves of K_{1, n}, neither missing leaf can ever be zero-forced.
We argue by induction on the definition of ZeroForced. In the base case, any vertex initially in S cannot equal either missing leaf because neither is in S. In the inductive step, suppose vertex u forces w. If w were one of the missing leaves (say j), u cannot be a leaf because there are no edges between leaves in the bipartite graph K_{1, n}. Nor can u be the center vertex, since forcing leaf j would require all other neighbors of the center to be already forced, including the other missing leaf k, contradicting the induction hypothesis. Symmetrically, w cannot be k either.
intro v hv induction hv with | init v hv => constructor <;> intro h <;> subst v · exact hj hv · exact hk hv | step u w hu hadj hother ihu ihother => constructor · intro hw subst w cases u with | inl a => have h := ihother (Sum.inr k) (by simp [completeBipartiteGraph]) (by simpa using hjk.symm) exact h.2 rfl | inr a => simp [completeBipartiteGraph] at hadj · intro hw subst w cases u with | inl a => have h := ihother (Sum.inr j) (by simp [completeBipartiteGraph]) (by simpa using hjk) exact h.1 rfl | inr a => simp [completeBipartiteGraph] at hadj
Every zero forcing set S of K_{1, n} must contain at least n - 1 vertices (n ≤ |S| + 1).
Let M be the set of leaves missing from S. By star_missing_two, M cannot contain two distinct leaves, so |M| ≤ 1. Since there are n leaves in total and every leaf is either in S or in M, the set of all n leaves is contained in S ∪ M. It follows that n ≤ |S| + |M| ≤ |S| + 1, so |S| ≥ n - 1.
uses
star_missing_two,Finset.card_image_of_injective,Sum.inr_injective,le_trans,Finset.card_image_le,Finset.card_le_card,Finset.card_union_lelet M : Finset (Fin n) := Finset.univ.filter (fun j => Sum.inr j ∉ S) have hM : M.card ≤ 1 := by apply Finset.card_le_one.mpr intro j hj k hk by_contra hne have hj' : Sum.inr j ∉ S := (Finset.mem_filter.mp hj).2 have hk' : Sum.inr k ∉ S := (Finset.mem_filter.mp hk).2 exact (star_missing_two n S j k hne hj' hk' _ (hz (Sum.inr j))).1 rfl let L : Finset (Unit ⊕ Fin n) := Finset.univ.image Sum.inr let U : Finset (Unit ⊕ Fin n) := M.image Sum.inr have hL : L.card = n := by simp [L, Finset.card_image_of_injective _ Sum.inr_injective] have hU : U.card ≤ 1 := le_trans (Finset.card_image_le) hM have hsub : L ⊆ S ∪ U := by intro x hx simp only [L, Finset.mem_image, Finset.mem_univ, true_and] at hx obtain ⟨j, rfl⟩ := hx by_cases h : Sum.inr j ∈ S · exact Finset.mem_union_left U h · apply Finset.mem_union_right exact Finset.mem_image.mpr ⟨j, Finset.mem_filter.mpr ⟨Finset.mem_univ _, h⟩, rfl⟩ have hc := Finset.card_le_card hsub have hc' := Finset.card_union_le S U omega
The zero forcing polynomial has coefficient 0 at any degree k with k + 2 ≤ n.
The k-th coefficient of the zero forcing polynomial counts the zero forcing sets of cardinality k. By star_zfs_card_lower, any zero forcing set must have size at least n - 1. When k ≤ n - 2, no such zero forcing set exists, so the set of such subsets is empty and the coefficient is 0.
uses
tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter,star_zfs_card_lowerrw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] apply Finset.card_eq_zero.mpr apply Finset.eq_empty_iff_forall_notMem.mpr intro S hS have hS' := Finset.mem_filter.mp hS have hcard := Finset.mem_powersetCard_univ.mp hS'.1 have hlower := star_zfs_card_lower n S hS'.2 omega
A zero forcing set S of K_{1, n} of size n - 1 cannot contain the center vertex.
Suppose, for contradiction, that the center vertex belongs to S. As shown previously, the set M of leaves missing from S has |M| ≤ 1. If S already contains the center vertex as well as at least n - 1 leaves, then S together with the at most one missing leaf covers all 1 + n vertices of K_{1, n}. Comparing cardinalities yields 1 + n ≤ |S| + |M| ≤ (n - 1) + 1 = n, a contradiction.
uses
star_missing_two,le_trans,Finset.card_image_le,Finset.card_le_card,Finset.card_union_le,Finset.card_univ,Fintype.card_sum,Fintype.card_unit,Fintype.card_finintro hc let M : Finset (Fin n) := Finset.univ.filter (fun j => Sum.inr j ∉ S) have hM : M.card ≤ 1 := by apply Finset.card_le_one.mpr intro j hj k hk by_contra hne have hj' : Sum.inr j ∉ S := (Finset.mem_filter.mp hj).2 have hk' : Sum.inr k ∉ S := (Finset.mem_filter.mp hk).2 exact (star_missing_two n S j k hne hj' hk' _ (hz (Sum.inr j))).1 rfl let U : Finset (Unit ⊕ Fin n) := M.image Sum.inr have hU : U.card ≤ 1 := le_trans Finset.card_image_le hM have hsub : (Finset.univ : Finset (Unit ⊕ Fin n)) ⊆ S ∪ U := by intro x hx cases x with | inl a => cases a; exact Finset.mem_union_left U hc | inr j => by_cases h : Sum.inr j ∈ S · exact Finset.mem_union_left U h · apply Finset.mem_union_right exact Finset.mem_image.mpr ⟨j, Finset.mem_filter.mpr ⟨Finset.mem_univ _, h⟩, rfl⟩ have hv := Finset.card_le_card hsub have hv' := Finset.card_union_le S U simp only [Finset.card_univ, Fintype.card_sum, Fintype.card_unit, Fintype.card_fin] at hv omega
For n ≥ 1, the (n - 1)-th coefficient of the zero forcing polynomial is at most the n-th coefficient.
We define a mapping from zero forcing sets of size n - 1 to those of size n by adjoining the center vertex: S ↦ S ∪ {center}. By star_no_center, the center vertex is not in S, so adjoining it strictly increases the cardinality to n. Monotonicity of zero forcing sets guarantees that this superset is also a zero forcing set. Finally, the map is injective because removing the center vertex uniquely recovers S, since neither input set contained the center.
uses
tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter,Finset.card_le_card_of_injOn,star_no_center,Finset.card_insert_of_notMem,tree_zero_forcing_poly_lower_half_monotone_is_zero_forcing_set_mono,Finset.subset_insert,congrArgrw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter, tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] let G := completeBipartiteGraph Unit (Fin n) let A := (Finset.powersetCard (n-1) (Finset.univ : Finset (Unit ⊕ Fin n))).filter (fun (S : Finset (Unit ⊕ Fin n)) => is_zero_forcing_set G (S : Set (Unit ⊕ Fin n))) let B := (Finset.powersetCard n (Finset.univ : Finset (Unit ⊕ Fin n))).filter (fun (S : Finset (Unit ⊕ Fin n)) => is_zero_forcing_set G (S : Set (Unit ⊕ Fin n))) change A.card ≤ B.card apply Finset.card_le_card_of_injOn (fun S => insert (Sum.inl ()) S) · intro S hS have hS' := Finset.mem_filter.mp hS have hcard := Finset.mem_powersetCard_univ.mp hS'.1 have hcenter : Sum.inl () ∉ S := star_no_center n S (by omega) hS'.2 apply Finset.mem_filter.mpr constructor · apply Finset.mem_powersetCard_univ.mpr rw [Finset.card_insert_of_notMem hcenter, hcard] omega · apply tree_zero_forcing_poly_lower_half_monotone_is_zero_forcing_set_mono G _ hS'.2 exact Finset.coe_subset.mpr (Finset.subset_insert _ _) · intro S hS T hT heq have hS' := Finset.mem_filter.mp hS have hT' := Finset.mem_filter.mp hT have hScard := Finset.mem_powersetCard_univ.mp hS'.1 have hTcard := Finset.mem_powersetCard_univ.mp hT'.1 have hSc : Sum.inl () ∉ S := star_no_center n S (by omega) hS'.2 have hTc : Sum.inl () ∉ T := star_no_center n T (by omega) hT'.2 have h := congrArg (fun R : Finset (Unit ⊕ Fin n) => R.erase (Sum.inl ())) heq simpa [Finset.erase_insert, hSc, hTc] using h
The zero forcing polynomial has coefficient 0 at any degree k with k > n + 1.
The star graph K_{1, n} has exactly n + 1 vertices in total. Therefore, there are no subsets of vertices of size k when k > n + 1, so the powerset of size k is empty and the coefficient vanishes.
uses
tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter,Nat.add_commrw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] have he : Finset.powersetCard k (Finset.univ : Finset (Unit ⊕ Fin n)) = ∅ := by apply Finset.powersetCard_eq_empty.mpr simpa [Nat.add_comm] using hk simp [he]
The coefficient of degree n + 1 of the zero forcing polynomial is at most 1.
The coefficient counts zero forcing sets of size n + 1, which is bounded above by the total number of subsets of size n + 1 from a vertex set of size n + 1. That binomial coefficient is (n + 1) choose (n + 1) = 1.
uses
tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter,le_trans,Finset.card_filter_le,Finset.card_powersetCard,Nat.add_commrw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] refine le_trans (Finset.card_filter_le _ _) ?_ simp [Finset.card_powersetCard, Nat.add_comm]
For n > 0, the coefficient of degree n of the zero forcing polynomial is at least 1.
We exhibit an explicit zero forcing set of size n by taking all vertices except a single leaf (say leaf 0). This set S has size (n + 1) - 1 = n. The center vertex and all leaves other than leaf 0 belong to S, so they are already forced. The center vertex has only one unforced neighbor, leaf 0, and therefore forces leaf 0 in a single step. Thus S forces every vertex, showing the coefficient is at least 1.
uses
tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter,Finset.card_erase_of_mem,Finset.mem_univ,ZeroForced.step,ZeroForced.initrw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] apply Finset.card_pos.mpr let leaf : Unit ⊕ Fin n := Sum.inr ⟨0, hn⟩ let S : Finset (Unit ⊕ Fin n) := Finset.univ.erase leaf refine ⟨S, Finset.mem_filter.mpr ⟨?_, ?_⟩⟩ · apply Finset.mem_powersetCard_univ.mpr simp [S, Finset.card_erase_of_mem (Finset.mem_univ leaf)] · intro v by_cases hv : v = leaf · subst v apply ZeroForced.step (Sum.inl ()) leaf · apply ZeroForced.init simp [S, leaf] · simp [leaf, completeBipartiteGraph] · intro x hx hne apply ZeroForced.init simpa [S] using hne · apply ZeroForced.init simpa [S] using hv
The constant coefficient (degree 0) of the zero forcing polynomial is 0.
The only subset of size 0 is the empty set. An induction on the forcing relation proves that no vertex can ever be forced from the empty set: the base case requires the vertex to be in the empty set, and the induction step requires an already forced vertex to act as the forcer, neither of which can hold. Hence the empty set is not a zero forcing set, and the degree 0 coefficient is 0.
uses
tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filterhave none {V : Type} (G : SimpleGraph V) {v : V} (h : ZeroForced G ∅ v) : False := by induction h with | init v hv => exact hv | step u w hu hadj hx ihu ihx => exact ihu rw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] apply Finset.card_eq_zero.mpr apply Finset.eq_empty_iff_forall_notMem.mpr intro S hS have hs := Finset.mem_filter.mp hS have hc := Finset.mem_powersetCard_univ.mp hs.1 have he : S = ∅ := Finset.card_eq_zero.mp hc subst S apply none (completeBipartiteGraph Unit (Fin n)) simpa using hs.2 (Sum.inl ())
When n = 0, the zero forcing polynomial is unimodal with mode m = 1.
For n = 0, the graph has a single vertex and the mode is m = 1. Below the peak (i ≤ j ≤ 1), if i = 0 the coefficient is 0 by star_coeff_zero, which is ≤ coeff j; if i = j the inequality is trivial. Above the peak (1 ≤ i ≤ j), if j = 1 then i = j = 1; if j > 1 the j-th coefficient is 0 by star_coeff_high_zero, so coeff j ≤ coeff i.
uses
star_coeff_zero,Nat.zero_le,le_rfl,star_coeff_high_zeroby_cases hn : n = 0 · subst n refine ⟨1, ?_, ?_⟩ · intro i j hij hj by_cases hi : i = 0 · subst i rw [star_coeff_zero] exact Nat.zero_le _ · have : i = j := by omega subst j exact le_rfl · intro i j hi hij by_cases hj : j = 1 · have hi1 : i = 1 := by omega subst i subst j exact le_rfl · rw [star_coeff_high_zero 0 j (by omega)] exact Nat.zero_le _
When n ≥ 1, the coefficients are non-decreasing up to degree n: for i ≤ j ≤ n, coeff i ≤ coeff j.
If i + 2 ≤ n, then the i-th coefficient is 0 by star_coeff_low_zero, which is automatically ≤ coeff j. Otherwise, either i = j by reflexivity, or i = n - 1 and j = n, in which case the inequality coeff (n - 1) ≤ coeff n is given by star_coeff_penult_le.
uses
star_coeff_low_zero,Nat.zero_le,le_rfl,star_coeff_penult_le· have hn' : 1 ≤ n := by omega refine ⟨n, ?_, ?_⟩ · intro i j hij hj by_cases hi : i + 2 ≤ n · rw [star_coeff_low_zero n i hi] exact Nat.zero_le _ · by_cases h : i = j · subst j exact le_rfl · have hi' : i = n - 1 := by omega have hj' : j = n := by omega rw [hi', hj'] exact star_coeff_penult_le n hn'
When n ≥ 1, the coefficients are non-increasing from degree n onward: for n ≤ i ≤ j, coeff j ≤ coeff i.
If j > n + 1, the j-th coefficient vanishes by star_coeff_high_zero, so coeff j = 0 ≤ coeff i. Otherwise, either i = j, or i = n and j = n + 1. In this last case, coeff (n + 1) ≤ 1 by star_coeff_top_le_one and 1 ≤ coeff n by star_coeff_n_pos, so transitivity gives coeff (n + 1) ≤ coeff n. Together with the non-decreasing half, this establishes unimodality with peak m = n.
uses
star_coeff_high_zero,Nat.zero_le,le_rfl,le_trans,star_coeff_top_le_one,star_coeff_n_pos· intro i j hi hij by_cases hj : n + 1 < j · rw [star_coeff_high_zero n j hj] exact Nat.zero_le _ · by_cases h : i = j · subst j exact le_rfl · have hi' : i = n := by omega have hj' : j = n + 1 := by omega rw [hi', hj'] exact le_trans (star_coeff_top_le_one n) (star_coeff_n_pos n hn')
star_missing_two- If a vertex set in K_{1, n} misses two distinct leaves, neither missing leaf can ever be zero-forced.
Finset.card_image_of_injective- An injective map between finite sets preserves cardinality.
Sum.inr_injective- The right inclusion map into a sum type is injective.
le_trans- The less-than-or-equal relation is transitive.
Finset.card_image_le- The image of a finite set under any function has cardinality at most the cardinality of the original set.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most that of the superset.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities.
tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter- The k-th coefficient of the zero forcing polynomial of a finite graph equals the number of zero forcing sets of size k.
star_zfs_card_lower- Every zero forcing set of K_{1, n} has cardinality at least n - 1.
Finset.card_univ- The cardinality of the universal finset on a finite type equals the cardinality of the type.
Fintype.card_sum- The cardinality of a sum type is the sum of the cardinalities of its two component types.
Fintype.card_unit- The cardinality of the unit type is 1.
Fintype.card_fin- The cardinality of the finite type Fin n is n.
Finset.card_le_card_of_injOn- If a function maps a finite set injectively into another finite set, the domain set has cardinality at most the codomain set.
star_no_center- A zero forcing set of K_{1, n} of size n - 1 cannot contain the center vertex.
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by 1.
tree_zero_forcing_poly_lower_half_monotone_is_zero_forcing_set_mono- Any superset of a zero forcing set is also a zero forcing set.
Finset.subset_insert- Any finite set is a subset of the result of inserting an element into it.
congrArg- Equal inputs to a function produce equal outputs.
Nat.add_comm- Addition on natural numbers is commutative.
Finset.card_filter_le- The cardinality of a filtered subset of a finite set is at most the cardinality of the original set.
Finset.card_powersetCard- The number of subsets of size k of a finite set s is the binomial coefficient |s| choose k.
Finset.card_erase_of_mem- Removing an element that belongs to a finite set decreases its cardinality by 1.
Finset.mem_univ- Every element of a finite type is an element of the universal finset of that type.
ZeroForced.step- A vertex u forces an adjacent unforced vertex w if all other neighbors of u are already forced.
ZeroForced.init- Every vertex in the initial set is zero-forced.
star_coeff_zero- The degree 0 coefficient of the zero forcing polynomial of K_{1, n} is 0.
Nat.zero_le- Zero is less than or equal to any natural number.
le_rfl- The less-than-or-equal relation is reflexive.
star_coeff_high_zero- Every coefficient of the zero forcing polynomial of K_{1, n} of degree greater than n + 1 is 0.
star_coeff_low_zero- Every coefficient of the zero forcing polynomial of K_{1, n} of degree at most n - 2 is 0.
star_coeff_penult_le- For n ≥ 1, the coefficient of degree n - 1 in the zero forcing polynomial of K_{1, n} is at most the coefficient of degree n.
star_coeff_top_le_one- The coefficient of degree n + 1 in the zero forcing polynomial of K_{1, n} is at most 1.
star_coeff_n_pos- For n > 0, the coefficient of degree n in the zero forcing polynomial of K_{1, n} is at least 1.
- The star graph K_{1, n} is formalized as completeBipartiteGraph Unit (Fin n), where Unit represents the single center vertex and Fin n represents the n leaves.
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.
open scoped Classicalopen Polynomiallemma star_missing_two (n : ℕ) (S : Set (Unit ⊕ Fin n)) (j k : Fin n) (hjk : j ≠ k) (hj : Sum.inr j ∉ S) (hk : Sum.inr k ∉ S) : ∀ v, ZeroForced (completeBipartiteGraph Unit (Fin n)) S v → v ≠ Sum.inr j ∧ v ≠ Sum.inr k := by intro v hv induction hv with | init v hv => constructor <;> intro h <;> subst v · exact hj hv · exact hk hv | step u w hu hadj hother ihu ihother => constructor · intro hw subst w cases u with | inl a => have h := ihother (Sum.inr k) (by simp [completeBipartiteGraph]) (by simpa using hjk.symm) exact h.2 rfl | inr a => simp [completeBipartiteGraph] at hadj · intro hw subst w cases u with | inl a => have h := ihother (Sum.inr j) (by simp [completeBipartiteGraph]) (by simpa using hjk) exact h.1 rfl | inr a => simp [completeBipartiteGraph] at hadjlemma star_zfs_card_lower (n : ℕ) (S : Finset (Unit ⊕ Fin n)) (hz : is_zero_forcing_set (completeBipartiteGraph Unit (Fin n)) (S : Set (Unit ⊕ Fin n))) : n ≤ S.card + 1 := by let M : Finset (Fin n) := Finset.univ.filter (fun j => Sum.inr j ∉ S) have hM : M.card ≤ 1 := by apply Finset.card_le_one.mpr intro j hj k hk by_contra hne have hj' : Sum.inr j ∉ S := (Finset.mem_filter.mp hj).2 have hk' : Sum.inr k ∉ S := (Finset.mem_filter.mp hk).2 exact (star_missing_two n S j k hne hj' hk' _ (hz (Sum.inr j))).1 rfl let L : Finset (Unit ⊕ Fin n) := Finset.univ.image Sum.inr let U : Finset (Unit ⊕ Fin n) := M.image Sum.inr have hL : L.card = n := by simp [L, Finset.card_image_of_injective _ Sum.inr_injective] have hU : U.card ≤ 1 := le_trans (Finset.card_image_le) hM have hsub : L ⊆ S ∪ U := by intro x hx simp only [L, Finset.mem_image, Finset.mem_univ, true_and] at hx obtain ⟨j, rfl⟩ := hx by_cases h : Sum.inr j ∈ S · exact Finset.mem_union_left U h · apply Finset.mem_union_right exact Finset.mem_image.mpr ⟨j, Finset.mem_filter.mpr ⟨Finset.mem_univ _, h⟩, rfl⟩ have hc := Finset.card_le_card hsub have hc' := Finset.card_union_le S U omegalemma star_coeff_low_zero (n k : ℕ) (hk : k + 2 ≤ n) : (zero_forcing_poly (completeBipartiteGraph Unit (Fin n))).coeff k = 0 := by rw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] apply Finset.card_eq_zero.mpr apply Finset.eq_empty_iff_forall_notMem.mpr intro S hS have hS' := Finset.mem_filter.mp hS have hcard := Finset.mem_powersetCard_univ.mp hS'.1 have hlower := star_zfs_card_lower n S hS'.2 omegalemma star_no_center (n : ℕ) (S : Finset (Unit ⊕ Fin n)) (hcard : S.card + 1 = n) (hz : is_zero_forcing_set (completeBipartiteGraph Unit (Fin n)) (S : Set (Unit ⊕ Fin n))) : Sum.inl () ∉ S := by intro hc let M : Finset (Fin n) := Finset.univ.filter (fun j => Sum.inr j ∉ S) have hM : M.card ≤ 1 := by apply Finset.card_le_one.mpr intro j hj k hk by_contra hne have hj' : Sum.inr j ∉ S := (Finset.mem_filter.mp hj).2 have hk' : Sum.inr k ∉ S := (Finset.mem_filter.mp hk).2 exact (star_missing_two n S j k hne hj' hk' _ (hz (Sum.inr j))).1 rfl let U : Finset (Unit ⊕ Fin n) := M.image Sum.inr have hU : U.card ≤ 1 := le_trans Finset.card_image_le hM have hsub : (Finset.univ : Finset (Unit ⊕ Fin n)) ⊆ S ∪ U := by intro x hx cases x with | inl a => cases a; exact Finset.mem_union_left U hc | inr j => by_cases h : Sum.inr j ∈ S · exact Finset.mem_union_left U h · apply Finset.mem_union_right exact Finset.mem_image.mpr ⟨j, Finset.mem_filter.mpr ⟨Finset.mem_univ _, h⟩, rfl⟩ have hv := Finset.card_le_card hsub have hv' := Finset.card_union_le S U simp only [Finset.card_univ, Fintype.card_sum, Fintype.card_unit, Fintype.card_fin] at hv omegalemma star_coeff_penult_le (n : ℕ) (hn : 1 ≤ n) : (zero_forcing_poly (completeBipartiteGraph Unit (Fin n))).coeff (n-1) ≤ (zero_forcing_poly (completeBipartiteGraph Unit (Fin n))).coeff n := by rw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter, tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] let G := completeBipartiteGraph Unit (Fin n) let A := (Finset.powersetCard (n-1) (Finset.univ : Finset (Unit ⊕ Fin n))).filter (fun (S : Finset (Unit ⊕ Fin n)) => is_zero_forcing_set G (S : Set (Unit ⊕ Fin n))) let B := (Finset.powersetCard n (Finset.univ : Finset (Unit ⊕ Fin n))).filter (fun (S : Finset (Unit ⊕ Fin n)) => is_zero_forcing_set G (S : Set (Unit ⊕ Fin n))) change A.card ≤ B.card apply Finset.card_le_card_of_injOn (fun S => insert (Sum.inl ()) S) · intro S hS have hS' := Finset.mem_filter.mp hS have hcard := Finset.mem_powersetCard_univ.mp hS'.1 have hcenter : Sum.inl () ∉ S := star_no_center n S (by omega) hS'.2 apply Finset.mem_filter.mpr constructor · apply Finset.mem_powersetCard_univ.mpr rw [Finset.card_insert_of_notMem hcenter, hcard] omega · apply tree_zero_forcing_poly_lower_half_monotone_is_zero_forcing_set_mono G _ hS'.2 exact Finset.coe_subset.mpr (Finset.subset_insert _ _) · intro S hS T hT heq have hS' := Finset.mem_filter.mp hS have hT' := Finset.mem_filter.mp hT have hScard := Finset.mem_powersetCard_univ.mp hS'.1 have hTcard := Finset.mem_powersetCard_univ.mp hT'.1 have hSc : Sum.inl () ∉ S := star_no_center n S (by omega) hS'.2 have hTc : Sum.inl () ∉ T := star_no_center n T (by omega) hT'.2 have h := congrArg (fun R : Finset (Unit ⊕ Fin n) => R.erase (Sum.inl ())) heq simpa [Finset.erase_insert, hSc, hTc] using hlemma star_coeff_high_zero (n k : ℕ) (hk : n + 1 < k) : (zero_forcing_poly (completeBipartiteGraph Unit (Fin n))).coeff k = 0 := by rw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] have he : Finset.powersetCard k (Finset.univ : Finset (Unit ⊕ Fin n)) = ∅ := by apply Finset.powersetCard_eq_empty.mpr simpa [Nat.add_comm] using hk simp [he]lemma star_coeff_top_le_one (n : ℕ) : (zero_forcing_poly (completeBipartiteGraph Unit (Fin n))).coeff (n+1) ≤ 1 := by rw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] refine le_trans (Finset.card_filter_le _ _) ?_ simp [Finset.card_powersetCard, Nat.add_comm]lemma star_coeff_n_pos (n : ℕ) (hn : 0 < n) : 1 ≤ (zero_forcing_poly (completeBipartiteGraph Unit (Fin n))).coeff n := by rw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] apply Finset.card_pos.mpr let leaf : Unit ⊕ Fin n := Sum.inr ⟨0, hn⟩ let S : Finset (Unit ⊕ Fin n) := Finset.univ.erase leaf refine ⟨S, Finset.mem_filter.mpr ⟨?_, ?_⟩⟩ · apply Finset.mem_powersetCard_univ.mpr simp [S, Finset.card_erase_of_mem (Finset.mem_univ leaf)] · intro v by_cases hv : v = leaf · subst v apply ZeroForced.step (Sum.inl ()) leaf · apply ZeroForced.init simp [S, leaf] · simp [leaf, completeBipartiteGraph] · intro x hx hne apply ZeroForced.init simpa [S] using hne · apply ZeroForced.init simpa [S] using hvlemma star_coeff_zero (n : ℕ) : (zero_forcing_poly (completeBipartiteGraph Unit (Fin n))).coeff 0 = 0 := by have none {V : Type} (G : SimpleGraph V) {v : V} (h : ZeroForced G ∅ v) : False := by induction h with | init v hv => exact hv | step u w hu hadj hx ihu ihx => exact ihu rw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter] apply Finset.card_eq_zero.mpr apply Finset.eq_empty_iff_forall_notMem.mpr intro S hS have hs := Finset.mem_filter.mp hS have hc := Finset.mem_powersetCard_univ.mp hs.1 have he : S = ∅ := Finset.card_eq_zero.mp hc subst S apply none (completeBipartiteGraph Unit (Fin n)) simpa using hs.2 (Sum.inl ())/-- The zero forcing polynomial of any star graph K_{1, n} is unimodal. -/theorem star_graph_zero_forcing_poly_unimodal (n : ℕ) : polynomial_is_unimodal (zero_forcing_poly (completeBipartiteGraph Unit (Fin n))) := by by_cases hn : n = 0 · subst n refine ⟨1, ?_, ?_⟩ · intro i j hij hj by_cases hi : i = 0 · subst i rw [star_coeff_zero] exact Nat.zero_le _ · have : i = j := by omega subst j exact le_rfl · intro i j hi hij by_cases hj : j = 1 · have hi1 : i = 1 := by omega subst i subst j exact le_rfl · rw [star_coeff_high_zero 0 j (by omega)] exact Nat.zero_le _ · have hn' : 1 ≤ n := by omega refine ⟨n, ?_, ?_⟩ · intro i j hij hj by_cases hi : i + 2 ≤ n · rw [star_coeff_low_zero n i hi] exact Nat.zero_le _ · by_cases h : i = j · subst j exact le_rfl · have hi' : i = n - 1 := by omega have hj' : j = n := by omega rw [hi', hj'] exact star_coeff_penult_le n hn' · intro i j hi hij by_cases hj : n + 1 < j · rw [star_coeff_high_zero n j hj] exact Nat.zero_le _ · by_cases h : i = j · subst j exact le_rfl · have hi' : i = n := by omega have hj' : j = n + 1 := by omega rw [hi', hj'] exact le_trans (star_coeff_top_le_one n) (star_coeff_n_pos n hn')