Existence of a Simple Graph of Order 20 with a Non-Unimodal Zero Forcing Polynomial
low tier2026-11-11OP-1400reviewed by Claude Code中文版
Abstract
The zero forcing polynomial $\mathcal{Z}(G; x) = \sum_{i=1}^n z(G, i) x^i$ of a graph $G$ of order $n$ counts its zero forcing sets by size. Whether it is always unimodal was asked in earlier work; arXiv:2611.11352 answered no with an infinite family, its smallest member having order 81, and asked for the smallest graph with a non-unimodal zero forcing polynomial. We give an explicit graph of order 20 whose zero forcing polynomial is not unimodal: Lean proves $z(G,15) \ge 932$, $z(G,16) \le 909$ and $z(G,17) \ge 939$, so the coefficients dip at 16. Exhaustive enumeration gives the whole polynomial, $420x^{14}+932x^{15}+909x^{16}+939x^{17}+180x^{18}+20x^{19}+x^{20}$. This brings the known upper bound on the smallest order from 81 down to 20.
1. Introduction
Zero forcing is a dynamic process on a graph that models the spread of information or color across vertices. Starting with an initial subset of vertices that are colored, the color change rule dictates that a colored vertex with exactly one uncolored neighbor forces that neighbor to become colored. A subset of vertices whose iterative closure under this rule colors all vertices in the graph is called a zero forcing set. The zero forcing number of a graph is the minimum cardinality of a zero forcing set, and it provides bounds on the maximum nullity of symmetric matrices associated with the graph.
Beyond the minimum cardinality, the distribution of all zero forcing sets by size provides a detailed combinatorial profile of the graph. For a finite simple graph $G = (V, E)$ of order $n = |V|$, this distribution is encoded in the zero forcing polynomial: $$\mathcal{Z}(G; x) = \sum_{i=1}^n z(G, i) x^i,$$ where $z(G, i)$ denotes the number of zero forcing sets of $G$ having cardinality $i$. The polynomial $\mathcal{Z}(G; x)$ is a generating function of zero forcing sets, with $z(G, i) = 0$ for all $i$ strictly less than the zero forcing number of $G$, and $z(G, n) = 1$ since the full vertex set $V$ always forms a zero forcing set.
A central question in the study of combinatorial polynomials is unimodality. A polynomial with non-negative real coefficients is called unimodal if its sequence of coefficients non-decreases up to a maximum index (a mode) and non-increases thereafter. Many classical graph polynomials, such as matching polynomials, independence polynomials for certain graph classes, and chromatic polynomials under suitable transformations, exhibit unimodality or log-concavity. Whether the zero forcing polynomial $\mathcal{Z}(G; x)$ is unimodal for every finite simple graph $G$ was asked in earlier work, which also showed that the first half of the coefficient sequence is always non-decreasing.
In arXiv:2611.11352, it was shown that zero forcing polynomials are not unimodal in general. The paper introduced an explicit family of constructions and showed that a specific graph denoted $G_{24,24,23}$ has order 81 and possesses a non-unimodal zero forcing polynomial. The family itself is non-unimodal from order 82 on; the order-81 graph is a smaller variant of it.
Section 3 of arXiv:2611.11352 then poses Question 2: "What is the smallest graph with a non-unimodal zero forcing polynomial?" The order-81 graph was the smallest example known, so a first step is whether a counterexample of order at most 80 exists at all.
This post presents a formal verification settling the order-at-most-80 question. We describe the theorem op_1400_counterexample_order_le_eighty, verified in the Lean 4 proof assistant, which proves that there exists a simple graph $G$ on Fin $n$ with $n \le 80$ whose zero forcing polynomial is not unimodal. In fact, the witness graph has order $n = 20$, which is substantially smaller than the threshold of 80 and the original counterexample of order 81. The polynomial of this 20-vertex graph is: $$\mathcal{Z}(G; x) = 420 x^{14} + 932 x^{15} + 909 x^{16} + 939 x^{17} + 180 x^{18} + 20 x^{19} + x^{20}.$$ The coefficient sequence exhibits a drop from $z(G, 15) \ge 932$ to $z(G, 16) \le 909$, followed by an increase to $z(G, 17) \ge 939$. This interior dip mathematically precludes unimodality.
2. Preliminaries
We consider finite simple graphs and the formalization of their zero forcing polynomials in Lean 4. Throughout, a simple graph $G$ on a vertex type $V$ is represented by the Mathlib type SimpleGraph $V$, which consists of an irreflexive and symmetric binary relation $G\text{.Adj} : V \to V \to \text{Prop}$. For finite graphs, the vertex set is equipped with an instance of Fintype $V$. The zero forcing process, the zero forcing sets, the zero forcing polynomial, and unimodality are defined as follows.
Definition 1 (ZeroForced): Let $G$ be a simple graph on a type $V$, and let $S \subseteq V$ be a subset of vertices. The zero forcing closure of $S$ in $G$ is the subset of vertices colored by the iterative application of the color change rule. In Lean, this closure is formalized by the inductive predicate ZeroForced $G\ S : V \to \text{Prop}$, defined by two constructors:
- The constructor init states that every vertex in the initial seed set $S$ belongs to the closure: $v \in S \to \text{ZeroForced } G\, S\, v$.
- The constructor step states that if a vertex $u$ is already in the closure, $u$ is adjacent to $w$, and every neighbor $x$ of $u$ other than $w$ is already in the closure, then $w$ enters the closure: $\text{ZeroForced } G\, S\, u \to G\text{.Adj } u\, w \to (\forall x, G\text{.Adj } u\, x \to x \ne w \to \text{ZeroForced } G\, S\, x) \to \text{ZeroForced } G\, S\, w$.
Remark: The rule requires that all neighbors of $u$ except $w$ are already forced; once that condition holds, $w$ is forced in a single step.
Definition 2 (is_zero_forcing_set): Let $G$ be a simple graph on a type $V$, and let $S \subseteq V$ be a subset of vertices. The set $S$ is a zero forcing set of $G$ if its zero forcing closure contains all vertices of $G$. In Lean, this property is defined by is_zero_forcing_set: $$\text{is\_zero\_forcing\_set}(G, S) \iff \forall v : V,\; \text{ZeroForced } G\, S\, v.$$ Here $S$ is viewed as a subset of type Set $V$, and the condition asserts that every vertex $v : V$ satisfies ZeroForced $G\ S\ v$.
Definition 3 (zero_forcing_poly): Let $V$ be a finite type equipped with Fintype $V$, and let $G$ be a simple graph on $V$. The zero forcing polynomial of $G$ is the generating function whose $k$-th coefficient is the number of zero forcing sets of cardinality $k$. In Lean, this is formalized as an element of Polynomial $\mathbb{N}$ via zero_forcing_poly: $$\mathcal{Z}(G; X) = \sum_{S : \text{Finset } V} \text{if } \text{is\_zero\_forcing\_set}(G, S) \text{ then } X^{|S|} \text{ else } 0.$$ In Lean's definition of zero_forcing_poly, this corresponds to summing over all elements of Finset $V$. Remark: The polynomial is defined over the natural numbers $\mathbb{N}$ using Polynomial $\mathbb{N}$. Because decidability of is_zero_forcing_set is not assumed globally, the definition opens classical logic to define the indicator function via a conditional expression. The polynomial variable is the formal indeterminate Polynomial.X. Subsets are drawn from Finset $V$.
Definition 4 (polynomial_is_unimodal): A polynomial $p \in \text{Polynomial } \mathbb{N}$ with natural coefficients is unimodal if there exists a mode $m \in \mathbb{N}$ such that its coefficients weakly increase up to $m$ and weakly decrease thereafter. In Lean, this is defined by polynomial_is_unimodal: $$\exists m : \mathbb{N},\; (\forall i \le j \le m,\; p\text{.coeff } i \le p\text{.coeff } j) \land (\forall m \le i \le j,\; p\text{.coeff } j \le p\text{.coeff } i).$$ Remark: Weak inequalities ($\le$) are used for both the non-decreasing and non-increasing phases. The mode $m$ is indexed by $\mathbb{N}$. In Mathlib, the coefficient $p\text{.coeff } k$ evaluates to 0 for any index $k$ exceeding the degree of $p$. Consequently, the weak monotonicity condition for $j \ge i \ge m$ holds naturally for indices past the degree, where all terms vanish.
3. Main result
The main theorem resolves the order-at-most-80 question by exhibiting an explicit counterexample of order 20.
Theorem (op_1400_counterexample_order_le_eighty): There exists a natural number $n \le 80$ and a simple graph $G$ on the vertex set Fin $n$ with decidable adjacency relation whose zero forcing polynomial is not unimodal: $$\exists (n : \mathbb{N})\; (\_ : n \le 80)\; (G : \text{SimpleGraph } (\text{Fin } n))\; (\_ : \text{DecidableRel } G.\text{Adj}),\; \neg\, \text{polynomial_is_unimodal } (\text{zero_forcing_poly } G).$$
The Lean statement op_1400_counterexample_order_le_eighty reads the English theorem by existentially quantifying over a natural number $n$, an inequality constraint $n \le 80$, a simple graph $G$ on the type Fin $n$, and an instance of decidable adjacency DecidableRel $G\text{.Adj}$, asserting that the zero forcing polynomial zero_forcing_poly $G$ is not unimodal according to polynomial_is_unimodal.
The witness graph $G$ has vertex set $\{0, \dots, 19\}$ and 135 edges: two distinct vertices are adjacent unless they form one of the following 55 pairs, $${0,1}, {0,4}, {0,5}, {0,6}, {0,8}, {0,9}, {1,8}, {1,9}, {2,3}, {2,7}, {2,8}, {2,9}, {3,7}, {3,8}, {3,9}, {4,5}, {4,6}, {4,7}, {5,6}, {5,7}, {6,7}, {10,11}, {10,12}, {10,13}, {10,14}, {10,15}, {10,16}, {10,17}, {11,12}, {11,13}, {11,14}, {11,15}, {11,16}, {11,17}, {12,13}, {12,14}, {12,15}, {12,16}, {12,17}, {13,15}, {13,16}, {13,17}, {13,19}, {14,15}, {14,16}, {14,17}, {14,19}, {15,16}, {15,17}, {15,18}, {15,19}, {16,17}, {16,18}, {16,19}, {17,18}.$$ Its twin classes (vertices with the same neighbours outside the pair) are $\{2,3\}$, $\{4,5,6\}$, $\{8,9\}$, $\{10,11,12\}$, $\{13,14\}$, $\{15,16\}$ and six singletons, so $G$ is a blow-up of a 12-vertex graph. By exhaustive enumeration (a computation outside Lean), its zero forcing polynomial is: $$\mathcal{Z}(G; X) = 420 X^{14} + 932 X^{15} + 909 X^{16} + 939 X^{17} + 180 X^{18} + 20 X^{19} + X^{20}.$$ So its zero forcing number is 14. Lean does not prove these exact values; it proves the three bounds below, which are all that non-unimodality needs.
The non-unimodality of $G$ is witnessed by the three coefficients at degrees 15, 16, and 17, which satisfy: $$z(G, 15) \ge 932,\quad z(G, 16) \le 909,\quad z(G, 17) \ge 939.$$ Because $z(G, 15) > z(G, 16)$ and $z(G, 16) < z(G, 17)$, the coefficient sequence dips strictly at index 16. If the polynomial were unimodal with some mode $m$, then $m \le 16$ would force $z(G, 16) \ge z(G, 17)$, while $m \ge 16$ would force $z(G, 15) \le z(G, 16)$, both of which contradict the bounds. So a graph of order 20 has a non-unimodal zero forcing polynomial.
theorem op_1400_counterexample_order_le_eighty :
∃ (n : ℕ) (_ : n ≤ 80) (G : SimpleGraph (Fin n)) (_ : DecidableRel G.Adj),
¬ polynomial_is_unimodal (zero_forcing_poly G)4. Proof
Three facts give the result. If $p\text{.coeff } b < p\text{.coeff } a$ and $p\text{.coeff } b < p\text{.coeff } c$ for $a < b < c$, then $p$ is not unimodal: a mode $m \ge b$ would give $p\text{.coeff } a \le p\text{.coeff } b$, and a mode $m \le b$ would give $p\text{.coeff } c \le p\text{.coeff } b$. It remains to prove $z(G,15) \ge 932$, $z(G,16) \le 909$ and $z(G,17) \ge 939$.
From sets to their complements. A set $S$ of size $k$ is counted by $z(G,k)$ exactly when its complement $W$, a set of $20-k$ white vertices, is cleared by the color change rule when all of $S$ starts blue. So $z(G,k)$ is the number of $(20-k)$-subsets $W$ of $\{0,\dots,19\}$ whose forcing process starting from the complement colors everything. The proof encodes $W$ as a 20-bit mask, and the graph as one natural number holding the 20 adjacency rows.
A checked forcing procedure. A computable procedure repeatedly looks for a blue vertex $v$ whose white neighbors, the mask $N(v) \wedge W$, form a single bit, and clears that bit. Two facts are proved about it in general, not by computation:
- *Soundness.* Every vertex that the procedure turns blue satisfies the inductive closure predicate. In particular, if the white mask becomes empty, then $S$ is a zero forcing set.
- *Completeness.* If the procedure stops with a nonempty white set $F$, then no blue vertex has exactly one neighbor in $F$, so $F$ is a fort. Induction on the closure predicate then shows that no vertex of $F$ is ever forced, so $S$ is not a zero forcing set.
To certify a stop quickly, the procedure computes the union $u_1$ of the neighborhoods of the white vertices and the set $u_2$ of vertices with at least two white neighbors. An invariant about these unions shows that if no blue vertex lies in $u_1$ but outside $u_2$, then no blue vertex has a single white neighbor.
Counting. Soundness gives a pointwise lower bound on the indicator of "zero forcing", and completeness gives a pointwise upper bound. A recursive enumerator sums these bounds over the $k$-subsets of $\{0,\dots,19\}$. It is proved equal to the corresponding sum over the binomial subsets of $\{0,\dots,19\}$, and it splits into partial sums by the largest elements of the subsets. Each partial sum is evaluated by the Lean kernel; the largest one covers 969 subsets.
- For $k = 17$, all 1140 sets of 3 white vertices are evaluated, giving $z(G,17) \ge 939$.
- For $k = 16$, the upper-bound sum over all 4845 sets of 4 white vertices is 909, giving $z(G,16) \le 909$.
- For $k = 15$, only a lower bound is needed. After a relabelling of the vertices, the 5-sets with good complements all have their two largest elements in 9 blocks covering 5221 of the 15504 five-sets. Those blocks alone give $z(G,15) \ge 932$.
With these three bounds the dip at 16 follows, and the existential statement is witnessed by $n = 20$ and this graph.
5. Discussion
The result formalized in theorem op_1400_counterexample_order_le_eighty resolves the specific question posed in Section 3, Question 2 of arXiv:2611.11352: whether there exists a graph of order at most 80 with a non-unimodal zero forcing polynomial. Before this, the smallest known example was the order-81 graph of arXiv:2611.11352; non-unimodal zero forcing polynomials already occur at order 20. The graph was found by a local search over blow-ups of small graphs, in which every vertex is replaced by a clique or an independent set of twins. Two white vertices in one twin class form a fort, so a good white set takes at most one vertex from each class, and the top coefficients become polynomials in the class sizes. The same search also found a graph of order 19 whose coefficients dip at index 15 ($780 > 754 < 780$). That example was checked by enumeration but is not formalized.
However, the result does not settle the broader question raised in Section 3, Question 2 of arXiv:2611.11352, which asks for the minimum order of a simple graph with a non-unimodal zero forcing polynomial. The Lean theorem gives the upper bound 20 on this minimum order (19 by the unformalized example). Whether smaller counterexamples exist is open. Specifically:
- Is the zero forcing polynomial $\mathcal{Z}(G; x)$ unimodal for all simple graphs $G$ of order $n \le 19$?
- What is the exact minimum order $n$ such that some simple graph of order $n$ has a non-unimodal zero forcing polynomial?
The theorem verifies a single instance; no enumeration of small graphs was done, so the exact minimum order is undetermined.
In addition to the order, the structural properties of graphs with non-unimodal zero forcing polynomials remain to be explored. In the order-20 graph the zero forcing number is 14, and the failure of unimodality occurs near the top of the spectrum, with coefficients dipping from degree 15 to degree 16 before rising again at degree 17. No general construction is given here, and no attempt is made to identify graph-theoretic characteristics—such as connectivity, maximum degree, or forbidden subgraphs—that necessitate or prevent non-unimodality. Determining the minimum order and identifying structural conditions under which zero forcing polynomials are guaranteed to be unimodal are the key open questions following from this work.
Why it is research-level
- Settles the order-at-most-80 question of OP-1400: an explicit graph on 20 vertices has a non-unimodal zero forcing polynomial (z(15) >= 932 > z(16) <= 909 < z(17) >= 939; exactly 420x^14+932x^15+909x^16+939x^17+180x^18+20x^19+x^20), far below the order-81 example of the source paper
Lean declarations
- op_1400_counterexample_order_le_eightyOpen Problem OP-1400: there exists a natural number n ≤ 80 and a simple graph G on Fin n with decidable adjacency whose zero forcing…
- 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.
- 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…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2611.11352 — Zero forcing is not unimodal
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.