AFTD Auto-Formalizing Theoretical Domains

star_graph_zero_forcing_poly_unimodal

theoremverifiedformalization

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.

  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.

    lines 9–30

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

    lines 35–58

    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_le

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

    lines 62–69

    uses tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter, star_zfs_card_lower

      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
      omega
  4. 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.

    lines 75–98

    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_fin

      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
      omega
  5. 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.

    lines 103–131

    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, congrArg

      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 h
  6. 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.

    lines 135–139

    uses tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter, Nat.add_comm

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

    lines 143–145

    uses tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter, le_trans, Finset.card_filter_le, Finset.card_powersetCard, Nat.add_comm

      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]
  8. 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.

    lines 149–167

    uses tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter, Finset.card_erase_of_mem, Finset.mem_univ, ZeroForced.step, ZeroForced.init

      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 hv
  9. 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.

    lines 171–184

    uses tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter

      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 ())
  10. 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.

    lines 189–207

    uses star_coeff_zero, Nat.zero_le, le_rfl, star_coeff_high_zero

      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 _
  11. 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.

    lines 208–220

    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'
  12. 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.

    lines 221–231

    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.

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

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