AFTD Auto-Formalizing Theoretical Domains

tree_zero_forcing_poly_lower_half_monotone

theoremverifiedformalization

For 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 to the coefficient of $X^{i+1}$ for every integer $i$ satisfying $1 \le i < \lfloor (|V| + 1) / 2 \rfloor$ (i.e., using integer division).

Statement

theorem tree_zero_forcing_poly_lower_half_monotone
    {V : Type*} [Fintype V] (T : SimpleGraph V) (hT : T.IsTree)
    (i : ℕ) (hi1 : 1 ≤ i) (hi2 : i < (Fintype.card V + 1) / 2) :
    (zero_forcing_poly T).coeff i ≤ (zero_forcing_poly T).coeff (i + 1)
Formalizes
arXiv:2611.11352 Sec. 1
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • 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.
  • ZeroForcedThe zero forcing closure of an initial set S of blue vertices in G under the color change rule.
Used by 1

Read back from the Lean

For any finite type $V$, any simple graph $T$ on $V$ such that $T$ is a tree (T.IsTree), and any natural number $i$ satisfying $1 \le i$ and $i < (|V| + 1) / 2$ (using integer division in $\mathbb{N}$), the $i$-th coefficient of the zero forcing polynomial of $T$ is less than or equal to its $(i + 1)$-th coefficient.

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 proof expresses the i-th and (i+1)-th coefficients of the zero forcing polynomial as the cardinalities |A| and |B| of the families of zero forcing sets of sizes i and i + 1, respectively. A bipartite double counting argument on inclusion pairs (s, x) ∈ A × B with s ⊆ x shows that |A| * (|V| - i) ≤ |B| * (i + 1), because every (i+1)-element superset of a zero forcing set is also zero forcing, while any (i+1)-element set contains at most i + 1 subsets of size i. The assumption i < ⌊(|V| + 1) / 2⌋ implies i + 1 ≤ |V| - i, allowing one to cancel the positive factor i + 1 and conclude that |A| ≤ |B|.

  1. Zero forcing is monotone under supersets: any superset of a zero forcing set is also a zero forcing set.

    By induction on the derivation that a vertex v is zero forced from S, every forcing step remains valid when starting from a larger initial set S' ⊇ S. Consequently, if S is a zero forcing set (forcing every vertex in V), any superset S' is also a zero forcing set.

    lines 4–14

    uses ZeroForced.init, ZeroForced.step, tree_zero_forcing_poly_lower_half_monotone_zero_forced_mono

    theorem tree_zero_forcing_poly_lower_half_monotone_zero_forced_mono {V : Type*} (G : SimpleGraph V) {S S' : Set V}
        (h : S ⊆ S') {v : V} (hv : ZeroForced G S v) : ZeroForced G S' v := by
      induction hv with
      | init x hx => exact ZeroForced.init x (h hx)
      | step u w hu hadj hx ihu ihx =>
        exact ZeroForced.step u w ihu hadj ihx
    
    theorem tree_zero_forcing_poly_lower_half_monotone_is_zero_forcing_set_mono {V : Type*} (G : SimpleGraph V) {S S' : Set V}
        (h : S ⊆ S') (hS : is_zero_forcing_set G S) : is_zero_forcing_set G S' :=
      fun v => tree_zero_forcing_poly_lower_half_monotone_zero_forced_mono G h (hS v)
    
  2. The coefficient of X^k in the zero forcing polynomial of G is the number of zero forcing sets of size k.

    By definition, the zero forcing polynomial sums X^|S| over all zero forcing sets S. Pushing the coefficient operator through the sum, the summand is 1 if S is a zero forcing set of cardinality k, and 0 otherwise. Rewriting this sum over all subsets as the sum of 1 over the family of zero forcing sets of size k shows that the coefficient equals the cardinality of this family.

    lines 15–45

    uses finsetSum_coeff, apply_ite, coeff_X_pow, Finset.mem_powersetCard_univ, Finset.card_eq_sum_ones, Finset.sum_subset, Finset.subset_univ

    lemma tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) :
        (zero_forcing_poly G).coeff k =
          ((Finset.powersetCard k (Finset.univ : Finset V)).filter
            (fun (S : Finset V) => is_zero_forcing_set G (S : Set V))).card := by
      dsimp [zero_forcing_poly]
      rw [finsetSum_coeff]
      simp_rw [apply_ite (fun p : Polynomial ℕ => coeff p k), coeff_zero, coeff_X_pow]
      let A : Finset (Finset V) := (Finset.powersetCard k (Finset.univ : Finset V)).filter
            (fun (S : Finset V) => is_zero_forcing_set G (S : Set V))
      have hA : ∀ S ∈ A, (if is_zero_forcing_set G (S : Set V) then if k = S.card then 1 else 0 else 0) = (1 : ℕ) := by
        intro S hS
        have hS' : S ∈ Finset.powersetCard k (Finset.univ : Finset V) ∧ is_zero_forcing_set G (S : Set V) :=
          Finset.mem_filter.mp hS
        rw [Finset.mem_powersetCard_univ] at hS'
        rw [if_pos hS'.2, if_pos hS'.1.symm]
      have hAc : ∀ S ∈ (Finset.univ : Finset (Finset V)), S ∉ A →
          (if is_zero_forcing_set G (S : Set V) then if k = S.card then 1 else 0 else 0) = (0 : ℕ) := by
        intro S _ hS
        have hS' : ¬ (S ∈ Finset.powersetCard k (Finset.univ : Finset V) ∧ is_zero_forcing_set G (S : Set V)) :=
          fun h => hS (Finset.mem_filter.mpr h)
        rw [Finset.mem_powersetCard_univ] at hS'
        by_cases hzf : is_zero_forcing_set G (S : Set V)
        · rw [if_pos hzf]
          have : ¬ k = S.card := fun hk => hS' ⟨hk.symm, hzf⟩
          rw [if_neg this]
        · rw [if_neg hzf]
      rw [Finset.card_eq_sum_ones]
      change (∑ x : Finset V, _) = ∑ x ∈ A, 1
      rw [Finset.sum_congr rfl (fun S hS => (hA S hS).symm)]
      exact (Finset.sum_subset (Finset.subset_univ A) (fun S hS hS_not => hAc S hS hS_not)).symm
    
  3. For any subset s of cardinality i, exactly |V| - i subsets of size i + 1 contain s.

    A subset of size i + 1 containing s is obtained by adjoining a single element from V \ s. By the standard formula for counting supersets of a fixed size, there are ((|V| - i) choose ((i + 1) - i)) = ((|V| - i) choose 1) = |V| - i such subsets.

    lines 46–57

    uses Finset.subset_univ, Finset.card_filter_powersetCard_subset, Finset.card_univ, Nat.choose_one_right

    lemma tree_zero_forcing_poly_lower_half_monotone_card_filter_powersetCard_succ {V : Type*} [Fintype V] (s : Finset V) (i : ℕ)
        (hs : s.card = i) :
        ((Finset.powersetCard (i + 1) (Finset.univ : Finset V)).filter (fun x => s ⊆ x)).card =
          Fintype.card V - i := by
      have hsub : s ⊆ Finset.univ := Finset.subset_univ s
      have hle : s.card ≤ i + 1 := hs ▸ Nat.le_succ i
      have := Finset.card_filter_powersetCard_subset s Finset.univ (i + 1) hsub hle
      rw [hs, Finset.card_univ] at this
      have h1 : i + 1 - i = 1 := by omega
      rw [h1, Nat.choose_one_right] at this
      exact this
    
  4. If s is a zero forcing set, every (i+1)-element superset of s is also a zero forcing set.

    Because zero forcing sets are upward-closed under inclusion, any superset x ⊇ s of a zero forcing set s is automatically a zero forcing set. Hence, restricting the family of (i+1)-element supersets of s to zero forcing sets discards nothing.

    lines 58–71

    uses Finset.mem_filter, Finset.coe_subset.mpr, tree_zero_forcing_poly_lower_half_monotone_is_zero_forcing_set_mono

    lemma tree_zero_forcing_poly_lower_half_monotone_filter_B_eq_filter_powersetCard {V : Type*} [Fintype V] (G : SimpleGraph V)
        (i : ℕ) (s : Finset V) (hsA : is_zero_forcing_set G (s : Set V)) :
        ((Finset.powersetCard (i + 1) (Finset.univ : Finset V)).filter
            (fun (x : Finset V) => is_zero_forcing_set G (x : Set V))).filter (fun x => s ⊆ x) =
          (Finset.powersetCard (i + 1) (Finset.univ : Finset V)).filter (fun x => s ⊆ x) := by
      ext x
      simp only [Finset.mem_filter]
      constructor
      · rintro ⟨⟨hx_pow, _⟩, hsx⟩
        exact ⟨hx_pow, hsx⟩
      · rintro ⟨hx_pow, hsx⟩
        have hsub : (s : Set V) ⊆ (x : Set V) := Finset.coe_subset.mpr hsx
        exact ⟨⟨hx_pow, tree_zero_forcing_poly_lower_half_monotone_is_zero_forcing_set_mono G hsub hsA⟩, hsx⟩
    
  5. Any subset x of cardinality i + 1 contains at most i + 1 zero forcing subsets of cardinality i.

    The zero forcing subsets of x of size i form a subcollection of all i-element subsets of x. Since x has size i + 1, it has exactly ((i + 1) choose i) = i + 1 subsets of size i, giving the upper bound.

    lines 72–89

    uses Finset.card_le_card, Finset.card_powersetCard, Nat.choose_succ_self_right

    lemma tree_zero_forcing_poly_lower_half_monotone_card_filter_A_sub {V : Type*} [Fintype V] (G : SimpleGraph V) (x : Finset V) (i : ℕ)
        (hx : x.card = i + 1) :
        (((Finset.powersetCard i (Finset.univ : Finset V)).filter
            (fun (s : Finset V) => is_zero_forcing_set G (s : Set V))).filter (fun s => s ⊆ x)).card ≤ i + 1 := by
      have hsub : ((Finset.powersetCard i (Finset.univ : Finset V)).filter
            (fun (s : Finset V) => is_zero_forcing_set G (s : Set V))).filter (fun s => s ⊆ x) ⊆
          (Finset.powersetCard i (Finset.univ : Finset V)).filter (fun s => s ⊆ x) := by
        intro s hs
        simp only [Finset.mem_filter] at hs ⊢
        exact ⟨hs.1.1, hs.2⟩
      apply le_trans (Finset.card_le_card hsub)
      have heq : (Finset.powersetCard i (Finset.univ : Finset V)).filter (fun s => s ⊆ x) =
          Finset.powersetCard i x := by
        ext s
        simp only [Finset.mem_filter, Finset.mem_powersetCard, Finset.subset_univ, true_and]
        tauto
      rw [heq, Finset.card_powersetCard, hx, Nat.choose_succ_self_right]
    
  6. Express the polynomial coefficients as the sizes of families A and B, and establish the double-counting identity on inclusion pairs.

    Rewriting the coefficients of X^i and X^{i+1} via the coefficient lemma gives the cardinalities of A (zero forcing sets of size i) and B (zero forcing sets of size i + 1). Double counting the incidence pairs (s, x) ∈ A × B with s ⊆ x by interchanging the summation order yields ∑_{s ∈ A} |{x ∈ B : s ⊆ x}| = ∑_{x ∈ B} |{s ∈ A : s ⊆ x}|.

    lines 90–104

    uses tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter, Finset.card_filter, Finset.sum_comm

    /-- The lower half of the coefficients of the zero forcing polynomial of any finite tree is non-decreasing. -/
    theorem tree_zero_forcing_poly_lower_half_monotone
        {V : Type*} [Fintype V] (T : SimpleGraph V) (hT : T.IsTree)
        (i : ℕ) (hi1 : 1 ≤ i) (hi2 : i < (Fintype.card V + 1) / 2) :
        (zero_forcing_poly T).coeff i ≤ (zero_forcing_poly T).coeff (i + 1) := by
      rw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter T i,
          tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter T (i + 1)]
      let A := (Finset.powersetCard i (Finset.univ : Finset V)).filter
          (fun (s : Finset V) => is_zero_forcing_set T (s : Set V))
      let B := (Finset.powersetCard (i + 1) (Finset.univ : Finset V)).filter
          (fun (x : Finset V) => is_zero_forcing_set T (x : Set V))
      have h_sum : ∑ s ∈ A, (B.filter (fun x => s ⊆ x)).card =
          ∑ x ∈ B, (A.filter (fun s => s ⊆ x)).card := by
        simp_rw [Finset.card_filter]
        exact Finset.sum_comm
  7. The sum of out-degrees from A to B equals |A| * (|V| - i).

    For each s ∈ A, s is a zero forcing set of size i, so all |V| - i of its (i+1)-element supersets belong to B. Summing this constant over all s ∈ A gives |A| * (|V| - i).

    lines 105–117

    uses tree_zero_forcing_poly_lower_half_monotone_filter_B_eq_filter_powersetCard, tree_zero_forcing_poly_lower_half_monotone_card_filter_powersetCard_succ, Finset.sum_const, smul_eq_mul

      have h_left : ∑ s ∈ A, (B.filter (fun x => s ⊆ x)).card = A.card * (Fintype.card V - i) := by
        have h_each : ∀ s ∈ A, (B.filter (fun x => s ⊆ x)).card = Fintype.card V - i := by
          intro s hs
          have hs' : s ∈ Finset.powersetCard i (Finset.univ : Finset V) ∧ is_zero_forcing_set T (s : Set V) :=
            Finset.mem_filter.mp hs
          rw [Finset.mem_powersetCard_univ] at hs'
          have heq : B.filter (fun x => s ⊆ x) =
              (Finset.powersetCard (i + 1) (Finset.univ : Finset V)).filter (fun x => s ⊆ x) :=
            tree_zero_forcing_poly_lower_half_monotone_filter_B_eq_filter_powersetCard T i s hs'.2
          rw [heq]
          exact tree_zero_forcing_poly_lower_half_monotone_card_filter_powersetCard_succ s i hs'.1
        rw [Finset.sum_congr rfl h_each]
        simp only [Finset.sum_const, smul_eq_mul]
  8. The sum of in-degrees to B from A is at most |B| * (i + 1).

    Each x ∈ B has size i + 1 and therefore contains at most i + 1 subsets belonging to A. Summing this bound over all x ∈ B gives at most |B| * (i + 1).

    lines 118–126

    uses tree_zero_forcing_poly_lower_half_monotone_card_filter_A_sub, Finset.sum_le_card_nsmul, nsmul_eq_mul

      have h_right : ∑ x ∈ B, (A.filter (fun s => s ⊆ x)).card ≤ B.card * (i + 1) := by
        have h_each : ∀ x ∈ B, (A.filter (fun s => s ⊆ x)).card ≤ i + 1 := by
          intro x hx
          have hx' : x ∈ Finset.powersetCard (i + 1) (Finset.univ : Finset V) ∧ is_zero_forcing_set T (x : Set V) :=
            Finset.mem_filter.mp hx
          rw [Finset.mem_powersetCard_univ] at hx'
          exact tree_zero_forcing_poly_lower_half_monotone_card_filter_A_sub T x i hx'.1
        have := Finset.sum_le_card_nsmul B (fun x => (A.filter (fun s => s ⊆ x)).card) (i + 1) h_each
        rwa [nsmul_eq_mul] at this
  9. Combine the bounds to deduce |A| ≤ |B|, completing the proof.

    Equating the two sides of the double sum gives |A| * (|V| - i) ≤ |B| * (i + 1). The hypothesis i < ⌊(|V| + 1) / 2⌋ ensures that i + 1 ≤ |V| - i, which implies |A| * (i + 1) ≤ |A| * (|V| - i) ≤ |B| * (i + 1). Since i + 1 > 0, cancelling i + 1 yields |A| ≤ |B|.

    lines 127–133

    uses Nat.mul_le_mul_left, le_trans, Nat.le_of_mul_le_mul_right

      have h_mul : A.card * (Fintype.card V - i) ≤ B.card * (i + 1) := by
        rw [← h_left, h_sum]
        exact h_right
      have hle : i + 1 ≤ Fintype.card V - i := by omega
      have h1 : A.card * (i + 1) ≤ A.card * (Fintype.card V - i) := Nat.mul_le_mul_left A.card hle
      have h2 : A.card * (i + 1) ≤ B.card * (i + 1) := le_trans h1 h_mul
      exact Nat.le_of_mul_le_mul_right h2 (by omega)
ZeroForced.init
Every vertex in the initial set S is zero forced by S.
ZeroForced.step
If an already forced vertex u has exactly one unforced neighbor w, then w becomes zero forced.
tree_zero_forcing_poly_lower_half_monotone_zero_forced_mono
If S ⊆ S', any vertex zero forced from S is also zero forced from S'.
finsetSum_coeff
The n-th coefficient of a finite sum of polynomials is the sum of the n-th coefficients of the summands.
apply_ite
Applying a function to an if-then-else expression yields an if-then-else with the function applied to both branches.
coeff_X_pow
The coefficient of X^n in X^k is 1 if n = k and 0 otherwise.
Finset.mem_powersetCard_univ
A finite subset belongs to the powerset of size k if and only if its cardinality is k.
Finset.card_eq_sum_ones
The cardinality of a finite set equals the sum of 1 over all its elements.
Finset.sum_subset
A sum over a subset equals the sum over the superset if the summand vanishes outside the subset.
Finset.subset_univ
Every finite set of a given type is a subset of the universal finset of that type.
Finset.card_filter_powersetCard_subset
The number of n-element supersets of a set s contained in a finite set t is ((|t| - |s|) choose (n - |s|)).
Finset.card_univ
The cardinality of the universal finset is the cardinality of the underlying finite type.
Nat.choose_one_right
The binomial coefficient (n choose 1) equals n.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the original set and satisfies the predicate.
Finset.coe_subset.mpr
Subset inclusion of finsets implies subset inclusion of their coerced sets.
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.card_le_card
If s ⊆ t for finsets s and t, then |s| ≤ |t|.
Finset.card_powersetCard
The number of k-element subsets of a finset s is (|s| choose k).
Nat.choose_succ_self_right
The binomial coefficient ((n + 1) choose n) equals n + 1.
tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter
The coefficient of X^k in the zero forcing polynomial of G is the number of zero forcing sets of size k.
Finset.card_filter
The cardinality of a filtered finset equals the sum over the set of the indicator of the predicate.
Finset.sum_comm
The order of summation in a double sum over finite sets can be interchanged.
tree_zero_forcing_poly_lower_half_monotone_filter_B_eq_filter_powersetCard
If s is a zero forcing set, every (i+1)-element superset of s is also a zero forcing set.
tree_zero_forcing_poly_lower_half_monotone_card_filter_powersetCard_succ
For any subset s of cardinality i, the number of (i+1)-element subsets containing s is |V| - i.
Finset.sum_const
Summing a constant over a finite set equals the cardinality of the set times that constant.
smul_eq_mul
Scalar multiplication of natural numbers coincides with ordinary multiplication.
tree_zero_forcing_poly_lower_half_monotone_card_filter_A_sub
Any subset of cardinality i + 1 contains at most i + 1 zero forcing subsets of cardinality i.
Finset.sum_le_card_nsmul
If each term in a sum over a finset is bounded by n, the sum is at most the cardinality of the set times n.
nsmul_eq_mul
Scalar multiplication by a natural number is ordinary multiplication.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers by a factor k on the left preserves the inequality.
le_trans
The order relation ≤ is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Nat.le_of_mul_le_mul_right
If a * c ≤ b * c and c > 0 for natural numbers, then a ≤ b.

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 Polynomialtheorem tree_zero_forcing_poly_lower_half_monotone_zero_forced_mono {V : Type*} (G : SimpleGraph V) {S S' : Set V}    (h : S ⊆ S') {v : V} (hv : ZeroForced G S v) : ZeroForced G S' v := by  induction hv with  | init x hx => exact ZeroForced.init x (h hx)  | step u w hu hadj hx ihu ihx =>    exact ZeroForced.step u w ihu hadj ihxtheorem tree_zero_forcing_poly_lower_half_monotone_is_zero_forcing_set_mono {V : Type*} (G : SimpleGraph V) {S S' : Set V}    (h : S ⊆ S') (hS : is_zero_forcing_set G S) : is_zero_forcing_set G S' :=  fun v => tree_zero_forcing_poly_lower_half_monotone_zero_forced_mono G h (hS v)lemma tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) :    (zero_forcing_poly G).coeff k =      ((Finset.powersetCard k (Finset.univ : Finset V)).filter        (fun (S : Finset V) => is_zero_forcing_set G (S : Set V))).card := by  dsimp [zero_forcing_poly]  rw [finsetSum_coeff]  simp_rw [apply_ite (fun p : Polynomial ℕ => coeff p k), coeff_zero, coeff_X_pow]  let A : Finset (Finset V) := (Finset.powersetCard k (Finset.univ : Finset V)).filter        (fun (S : Finset V) => is_zero_forcing_set G (S : Set V))  have hA : ∀ S ∈ A, (if is_zero_forcing_set G (S : Set V) then if k = S.card then 1 else 0 else 0) = (1 : ℕ) := by    intro S hS    have hS' : S ∈ Finset.powersetCard k (Finset.univ : Finset V) ∧ is_zero_forcing_set G (S : Set V) :=      Finset.mem_filter.mp hS    rw [Finset.mem_powersetCard_univ] at hS'    rw [if_pos hS'.2, if_pos hS'.1.symm]  have hAc : ∀ S ∈ (Finset.univ : Finset (Finset V)), S ∉ A →      (if is_zero_forcing_set G (S : Set V) then if k = S.card then 1 else 0 else 0) = (0 : ℕ) := by    intro S _ hS    have hS' : ¬ (S ∈ Finset.powersetCard k (Finset.univ : Finset V) ∧ is_zero_forcing_set G (S : Set V)) :=      fun h => hS (Finset.mem_filter.mpr h)    rw [Finset.mem_powersetCard_univ] at hS'    by_cases hzf : is_zero_forcing_set G (S : Set V)    · rw [if_pos hzf]      have : ¬ k = S.card := fun hk => hS' ⟨hk.symm, hzf⟩      rw [if_neg this]    · rw [if_neg hzf]  rw [Finset.card_eq_sum_ones]  change (∑ x : Finset V, _) = ∑ x ∈ A, 1  rw [Finset.sum_congr rfl (fun S hS => (hA S hS).symm)]  exact (Finset.sum_subset (Finset.subset_univ A) (fun S hS hS_not => hAc S hS hS_not)).symmlemma tree_zero_forcing_poly_lower_half_monotone_card_filter_powersetCard_succ {V : Type*} [Fintype V] (s : Finset V) (i : ℕ)    (hs : s.card = i) :    ((Finset.powersetCard (i + 1) (Finset.univ : Finset V)).filter (fun x => s ⊆ x)).card =      Fintype.card V - i := by  have hsub : s ⊆ Finset.univ := Finset.subset_univ s  have hle : s.card ≤ i + 1 := hs ▸ Nat.le_succ i  have := Finset.card_filter_powersetCard_subset s Finset.univ (i + 1) hsub hle  rw [hs, Finset.card_univ] at this  have h1 : i + 1 - i = 1 := by omega  rw [h1, Nat.choose_one_right] at this  exact thislemma tree_zero_forcing_poly_lower_half_monotone_filter_B_eq_filter_powersetCard {V : Type*} [Fintype V] (G : SimpleGraph V)    (i : ℕ) (s : Finset V) (hsA : is_zero_forcing_set G (s : Set V)) :    ((Finset.powersetCard (i + 1) (Finset.univ : Finset V)).filter        (fun (x : Finset V) => is_zero_forcing_set G (x : Set V))).filter (fun x => s ⊆ x) =      (Finset.powersetCard (i + 1) (Finset.univ : Finset V)).filter (fun x => s ⊆ x) := by  ext x  simp only [Finset.mem_filter]  constructor  · rintro ⟨⟨hx_pow, _⟩, hsx⟩    exact ⟨hx_pow, hsx⟩  · rintro ⟨hx_pow, hsx⟩    have hsub : (s : Set V) ⊆ (x : Set V) := Finset.coe_subset.mpr hsx    exact ⟨⟨hx_pow, tree_zero_forcing_poly_lower_half_monotone_is_zero_forcing_set_mono G hsub hsA⟩, hsx⟩lemma tree_zero_forcing_poly_lower_half_monotone_card_filter_A_sub {V : Type*} [Fintype V] (G : SimpleGraph V) (x : Finset V) (i : ℕ)    (hx : x.card = i + 1) :    (((Finset.powersetCard i (Finset.univ : Finset V)).filter        (fun (s : Finset V) => is_zero_forcing_set G (s : Set V))).filter (fun s => s ⊆ x)).card ≤ i + 1 := by  have hsub : ((Finset.powersetCard i (Finset.univ : Finset V)).filter        (fun (s : Finset V) => is_zero_forcing_set G (s : Set V))).filter (fun s => s ⊆ x) ⊆      (Finset.powersetCard i (Finset.univ : Finset V)).filter (fun s => s ⊆ x) := by    intro s hs    simp only [Finset.mem_filter] at hs ⊢    exact ⟨hs.1.1, hs.2⟩  apply le_trans (Finset.card_le_card hsub)  have heq : (Finset.powersetCard i (Finset.univ : Finset V)).filter (fun s => s ⊆ x) =      Finset.powersetCard i x := by    ext s    simp only [Finset.mem_filter, Finset.mem_powersetCard, Finset.subset_univ, true_and]    tauto  rw [heq, Finset.card_powersetCard, hx, Nat.choose_succ_self_right]/-- The lower half of the coefficients of the zero forcing polynomial of any finite tree is non-decreasing. -/theorem tree_zero_forcing_poly_lower_half_monotone    {V : Type*} [Fintype V] (T : SimpleGraph V) (hT : T.IsTree)    (i : ℕ) (hi1 : 1 ≤ i) (hi2 : i < (Fintype.card V + 1) / 2) :    (zero_forcing_poly T).coeff i ≤ (zero_forcing_poly T).coeff (i + 1) := by  rw [tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter T i,      tree_zero_forcing_poly_lower_half_monotone_coeff_eq_card_filter T (i + 1)]  let A := (Finset.powersetCard i (Finset.univ : Finset V)).filter      (fun (s : Finset V) => is_zero_forcing_set T (s : Set V))  let B := (Finset.powersetCard (i + 1) (Finset.univ : Finset V)).filter      (fun (x : Finset V) => is_zero_forcing_set T (x : Set V))  have h_sum : ∑ s ∈ A, (B.filter (fun x => s ⊆ x)).card =      ∑ x ∈ B, (A.filter (fun s => s ⊆ x)).card := by    simp_rw [Finset.card_filter]    exact Finset.sum_comm  have h_left : ∑ s ∈ A, (B.filter (fun x => s ⊆ x)).card = A.card * (Fintype.card V - i) := by    have h_each : ∀ s ∈ A, (B.filter (fun x => s ⊆ x)).card = Fintype.card V - i := by      intro s hs      have hs' : s ∈ Finset.powersetCard i (Finset.univ : Finset V) ∧ is_zero_forcing_set T (s : Set V) :=        Finset.mem_filter.mp hs      rw [Finset.mem_powersetCard_univ] at hs'      have heq : B.filter (fun x => s ⊆ x) =          (Finset.powersetCard (i + 1) (Finset.univ : Finset V)).filter (fun x => s ⊆ x) :=        tree_zero_forcing_poly_lower_half_monotone_filter_B_eq_filter_powersetCard T i s hs'.2      rw [heq]      exact tree_zero_forcing_poly_lower_half_monotone_card_filter_powersetCard_succ s i hs'.1    rw [Finset.sum_congr rfl h_each]    simp only [Finset.sum_const, smul_eq_mul]  have h_right : ∑ x ∈ B, (A.filter (fun s => s ⊆ x)).card ≤ B.card * (i + 1) := by    have h_each : ∀ x ∈ B, (A.filter (fun s => s ⊆ x)).card ≤ i + 1 := by      intro x hx      have hx' : x ∈ Finset.powersetCard (i + 1) (Finset.univ : Finset V) ∧ is_zero_forcing_set T (x : Set V) :=        Finset.mem_filter.mp hx      rw [Finset.mem_powersetCard_univ] at hx'      exact tree_zero_forcing_poly_lower_half_monotone_card_filter_A_sub T x i hx'.1    have := Finset.sum_le_card_nsmul B (fun x => (A.filter (fun s => s ⊆ x)).card) (i + 1) h_each    rwa [nsmul_eq_mul] at this  have h_mul : A.card * (Fintype.card V - i) ≤ B.card * (i + 1) := by    rw [← h_left, h_sum]    exact h_right  have hle : i + 1 ≤ Fintype.card V - i := by omega  have h1 : A.card * (i + 1) ≤ A.card * (Fintype.card V - i) := Nat.mul_le_mul_left A.card hle  have h2 : A.card * (i + 1) ≤ B.card * (i + 1) := le_trans h1 h_mul  exact Nat.le_of_mul_le_mul_right h2 (by omega)
See it in the graphDiscuss this resultChallenge it