tree_zero_forcing_poly_lower_half_monotone
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
- star_graph_zero_forcing_poly_unimodalFor every natural number n, the complete bipartite graph K_{1, n} on Unit ⊕ Fin n has a unimodal zero forcing polynomial.
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|.
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.
uses
ZeroForced.init,ZeroForced.step,tree_zero_forcing_poly_lower_half_monotone_zero_forced_monotheorem 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)
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.
uses
finsetSum_coeff,apply_ite,coeff_X_pow,Finset.mem_powersetCard_univ,Finset.card_eq_sum_ones,Finset.sum_subset,Finset.subset_univlemma 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
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.
uses
Finset.subset_univ,Finset.card_filter_powersetCard_subset,Finset.card_univ,Nat.choose_one_rightlemma 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
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.
uses
Finset.mem_filter,Finset.coe_subset.mpr,tree_zero_forcing_poly_lower_half_monotone_is_zero_forcing_set_monolemma 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⟩
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.
uses
Finset.card_le_card,Finset.card_powersetCard,Nat.choose_succ_self_rightlemma 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]
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}|.
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
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).
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_mulhave 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]
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).
uses
tree_zero_forcing_poly_lower_half_monotone_card_filter_A_sub,Finset.sum_le_card_nsmul,nsmul_eq_mulhave 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
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|.
uses
Nat.mul_le_mul_left,le_trans,Nat.le_of_mul_le_mul_righthave 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.
- The assumption that T is a tree is never used in the proof; the result holds for any finite simple graph, and more generally for any upward-closed family of subsets in the Boolean lattice.
- The arithmetic inequalities relating i and |V| - i via the hypothesis i < ⌊(|V| + 1) / 2⌋ are handled by the omega decision procedure for Presburger arithmetic.
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 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)