Unimodality conjecture for graphical Stirling numbers of planar graphs

Counterexamples to planar graphical Stirling unimodality

Problem: MathDB #372912.

Primary source: Daniel Yaqubi and Madjid Mirzavaziri, On the Graphical $r$-Stirling Numbers of the First Kind for Specific Graph Families, arXiv:2602.02046, February 2026, Section 2 and Conjecture 6.1.

We disprove the conjecture in three progressively stronger ways: first by a connected planar graph whose entire coefficient sequence is strictly positive; then by infinitely many connected planar graphs with contiguous positive support; and finally by every sufficiently long cycle, which also exposes an inconsistency in the paper's assertion that the conjecture was already known for cycles.

1. The exact source convention

Let $G=(V,E)$ be a finite simple graph on $n$ vertices. A graphical cycle partition consists of disjoint blocks covering $V$. A singleton is a $1$-cycle, an adjacent pair is a $2$-cycle, and a block of size at least three carries a specific oriented Hamiltonian cycle in its induced subgraph. Thus different orientations or Hamiltonian cyclic orders of the same block are counted separately.

Equivalently, the relevant objects are precisely the permutations $\sigma\in S_V$ satisfying

$$\sigma(v)=v \quad\text{or}\quad \{v,\sigma(v)\}\in E \qquad (v\in V). \tag{1}$$

Indeed, a fixed point gives a singleton block, a transposition gives an adjacent $2$-cycle exactly once, and a longer permutation cycle gives the specified oriented Hamiltonian cycle. If $c(\sigma)$ is the number of permutation cycles, the source's graphical Stirling numbers and cycle polynomial are therefore

$$\begin{bmatrix}G\\k\end{bmatrix} =\#\{\sigma\in S_V:\sigma\text{ satisfies (1)},\ c(\sigma)=k\}, \qquad \mathcal C(G,x) =\sum_{k=1}^{n}\begin{bmatrix}G\\k\end{bmatrix}x^k. \tag{2}$$

This normalization is explicit in Section 2 of the source and is independently forced by its Theorem 3.9: for $G=K_n$, all permutations are allowed, so

$$\mathcal C(K_n,x)=x(x+1)\cdots(x+n-1). \tag{3}$$

For example, the two orientations of a triangle contribute the coefficient $2$ of $x$ in $\mathcal C(K_3,x)=x^3+3x^2+2x$.

The paper's Example 2.3 contains a separate normalization mistake: its displayed wheel vector $(8,9,14,8,1)$ counts proper triangles and $4$-cycles without their prescribed orientations. Applying the explicit definition and (3) consistently instead gives

$$\mathcal C(W_4,x)=8x+18x^2+18x^3+8x^4+x^5. \tag{4}$$

Our counterexamples use the explicit definition and the complete-graph normalization, rather than the inconsistent numerical example. The cycle counterexamples in Section 5 remain counterexamples even if every long cycle is counted without orientations.

2. A connected planar counterexample with every coefficient positive

Let $H$ have vertex set $\{0,1,2,3,4,5,6\}$ and edge set

$$E(H)= \bigl\{ 01,04,12,15,16,23,34,35,46,56 \bigr\}. \tag{5}$$

The graph is connected, since it contains the Hamiltonian cycle

$$0-1-2-3-5-6-4-0. \tag{6}$$

It is planar. For instance, the following five oriented facial walks define a spherical embedding:

$$\begin{aligned} F_1&=(0,4,3,2,1),& F_2&=(0,1,6,4),\\ F_3&=(1,2,3,5),& F_4&=(1,5,6),\\ F_5&=(4,6,5,3). \end{aligned} \tag{7}$$

Each edge occurs exactly twice, once in each direction; the incident facial corners form a single cyclic order at every vertex; and

$$|V(H)|-|E(H)|+|F(H)|=7-10+5=2. \tag{8}$$

Alternatively, an explicit straight-line planar drawing places the vertices at

$$\begin{array}{c|rrrrrrr} v&0&1&2&3&4&5&6\\ \hline x_v&0&2&5&6&10&6&8\\ y_v&0&2&5&4&0&3&1. \end{array} \tag{9}$$

No pair of nonincident edges intersects in this drawing.

Enumerate the allowed permutations (1), grouping them by their cycle-length partitions. The complete count is as follows:

Number $k$ of cycles	Cycle-length partition	Number
$1$	$(7)$	$2$
$2$	$(6,1)$	$4$
$2$	$(5,2)$	$6$
$3$	$(5,1,1)$	$12$
$3$	$(4,2,1)$	$12$
$3$	$(3,2,2)$	$2$
$4$	$(4,1,1,1)$	$6$
$4$	$(3,2,1,1)$	$6$
$4$	$(2,2,2,1)$	$13$
$5$	$(3,1,1,1,1)$	$2$
$5$	$(2,2,1,1,1)$	$25$
$6$	$(2,1,1,1,1,1)$	$10$
$7$	$(1,1,1,1,1,1,1)$	$1$

Consequently,

$$\boxed{ \mathcal C(H,x) =2x+10x^2+26x^3+25x^4+27x^5+10x^6+x^7. } \tag{10}$$

Every coefficient is positive, but the three consecutive interior coefficients satisfy

$$\begin{bmatrix}H\\3\end{bmatrix} =26 > 25 =\begin{bmatrix}H\\4\end{bmatrix} < 27 =\begin{bmatrix}H\\5\end{bmatrix}. \tag{11}$$

Hence the full coefficient sequence

$$(2,10,26,25,27,10,1) \tag{12}$$

is not unimodal. In particular, this failure is not attributable to leading zeros, internal zeros, disconnectedness, or a nonplanar graph.

3. A general pendant-vertex identity

Let $G$ be any graph, let $v\in V(G)$, and obtain $G_t$ by attaching $t$ new pendant vertices to $v$. In every allowed permutation of $G_t$, each new vertex is either fixed or belongs to a transposition with $v$. At most one pendant vertex can be transposed with $v$.

If all pendant vertices are fixed, they contribute $t$ singleton cycles and the original vertices contribute an arbitrary cycle partition of $G$. If one pendant vertex is transposed with $v$, there are $t$ choices of this vertex; the transposition and the remaining $t-1$ fixed pendant vertices again contribute exactly $t$ cycles, while the remaining old vertices contribute a cycle partition of $G-v$. Therefore

$$\boxed{ \mathcal C(G_t,x) =x^t\bigl(\mathcal C(G,x)+t\mathcal C(G-v,x)\bigr). } \tag{13}$$

This identity follows directly from the source definition, requires no unproved structural assumptions, and remains valid under either orientation convention for cycles of length at least three.

4. Infinitely many connected planar counterexamples without internal zeros

Apply (13) to the planar graph $H$ in (5) at vertex $v=5$. Direct permutation-cycle enumeration on the six remaining vertices gives

$$\mathcal C(H-5,x) =6x^2+4x^3+11x^4+7x^5+x^6. \tag{14}$$

Write $H_t$ for the graph obtained from $H$ by attaching $t$ pendant vertices at vertex $5$. It is connected and planar for every integer $t\geq0$. Equations (10), (13), and (14) yield the exact formula

$$\boxed{ \mathcal C(H_t,x) =x^t\left( 2x+(10+6t)x^2+(26+4t)x^3 +(25+11t)x^4+(27+7t)x^5+(10+t)x^6+x^7 \right). } \tag{15}$$

The coefficients on its nonzero support are strictly positive and consecutive. For every $t\geq9$,

$$\begin{aligned} (10+6t)-(26+4t)&=2t-16>0,\\ (25+11t)-(26+4t)&=7t-1>0. \end{aligned} \tag{16}$$

Thus

$$\begin{bmatrix}H_t\\t+2\end{bmatrix} > \begin{bmatrix}H_t\\t+3\end{bmatrix} < \begin{bmatrix}H_t\\t+4\end{bmatrix} \qquad(t\geq9). \tag{17}$$

This gives connected planar counterexamples of every order $n\geq16$, with a strict valley entirely inside their contiguous positive coefficient support.

5. The paper's own cycle formula gives another infinite obstruction

There is an even simpler obstruction, although it has an internal zero. For the planar cycle graph $C_n$, any graphical cycle partition is either its full Hamiltonian cycle, with its two orientations, or a matching of ordinary edges together with fixed vertices. A matching with $m$ edges contributes $k=n-m$ cycles, and the number of such matchings in $C_n$ is

$$\frac{n}{n-m}\binom{n-m}{m} =\frac{n}{k}\binom{k}{n-k}. \tag{18}$$

Therefore the paper's Theorem 3.7 itself gives

$$\mathcal C(C_n,x) =2x+ \sum_{k=\lceil n/2\rceil}^{n} \frac{n}{k}\binom{k}{n-k}x^k. \tag{19}$$

For every $n\geq5$, the coefficient of $x$ equals $2$, the coefficient of $x^2$ equals $0$, and the coefficient of $x^{\lceil n/2\rceil}$ is positive. Consequently the complete sequence is not unimodal. The smallest cycle example is

$$\mathcal C(C_5,x)=2x+5x^3+5x^4+x^5, \qquad \left( \begin{bmatrix}C_5\\k\end{bmatrix} \right)_{k=1}^{5} =(2,0,5,5,1). \tag{20}$$

Replacing the oriented Hamiltonian cycle count $2$ by the unoriented count $1$ leaves the same internal-zero obstruction. Thus the conjecture fails even under the alternative normalization suggested by the source's inconsistent wheel example.

The sentence following Conjecture 6.1 states that unimodality is already known for cycles. Formula (19), proved earlier in that same paper, contradicts this assertion for every $n\geq5$. The seven-vertex counterexample (10) is stronger: under the actual first-kind definition, unimodality fails even when every coefficient is positive.

Status: Conjecture 6.1 is DISPROVED, including for connected planar graphs with strictly positive coefficients, and for infinitely many connected planar graphs with no internal zeros on their positive support.