Monotonicity conjecture for restricted graphical Stirling numbers

Restricted graphical Stirling numbers are coefficientwise monotone

Result. For every finite simple labeled graph and every fixed number of cycle blocks, the graphical restricted Stirling numbers decrease weakly as the nested distinguished vertex set grows. The precise loss at each step counts the cycle partitions in which the new distinguished vertex shares a block with an earlier distinguished vertex. This also completely identifies when an individual inequality is strict and when equality occurs.

The statement is Conjecture 6.3 of Daniel Yaqubi and Madjid Mirzavaziri, On the Graphical $r$-Stirling Numbers of the First Kind for Specific Graph Families, arXiv:2602.02046. Their Definition 4.1 specifies that the distinguished vertices are the first $r$ labeled vertices. Consequently, the distinguished sets for successive values of $r$ are nested; this detail is essential.

1. Nested distinguished sets

Let

$$V(G)=\{v_1,\ldots,v_n\}, \qquad R_r=\{v_1,\ldots,v_r\}.$$

Write $\mathcal P_k(G;R)$ for the collection of graphical cycle partitions of $V(G)$ into exactly $k$ blocks in which all vertices of $R$ occupy distinct blocks. Here the cycle blocks, including singleton blocks, edge blocks, and larger graphical cycle blocks, are exactly those of the source. Thus

$$\begin{bmatrix}G\\k\end{bmatrix}_r =|\mathcal P_k(G;R_r)|.$$

More generally, whenever $R\subseteq R'\subseteq V(G)$, every partition separating all vertices of $R'$ necessarily separates all vertices of $R$. Therefore

$$\mathcal P_k(G;R')\subseteq\mathcal P_k(G;R),$$

and hence

$$|\mathcal P_k(G;R')| \leq |\mathcal P_k(G;R)|.$$

Applying this to $R_r\subset R_{r+1}$ gives, simultaneously for every $1\leq k\leq n$,

$$\boxed{ \begin{bmatrix}G\\k\end{bmatrix}_{1} \geq \begin{bmatrix}G\\k\end{bmatrix}_{2} \geq\cdots\geq \begin{bmatrix}G\\k\end{bmatrix}_{k}. }$$

This proves the displayed conjecture for every finite simple graph.

The stronger coefficientwise generating-polynomial version follows as well. Set

$$\mathcal C_R(G,x) =\sum_{k=0}^{n}|\mathcal P_k(G;R)|x^k.$$

Then

$$R\subseteq R' \quad\Longrightarrow\quad \mathcal C_R(G,x)-\mathcal C_{R'}(G,x) \in\mathbb Z_{\geq0}[x].$$

2. The exact strictness criterion

Fix $r<k$, and put $w=v_{r+1}$. For each $1\leq i\leq r$, define

$$\mathcal B_{r,i}(G,k) =\left\{ \pi\in\mathcal P_k(G;R_r): v_i\text{ and }w\text{ lie in the same cycle block of }\pi \right\}.$$

The sets $\mathcal B_{r,i}(G,k)$ are pairwise disjoint: the vertices of $R_r$ already occupy distinct blocks, so the block containing $w$ contains at most one of them. Moreover, a partition counted at level $r$ fails the level-$r+1$ restriction precisely when it belongs to one of these sets. Consequently,

$$\boxed{ \begin{bmatrix}G\\k\end{bmatrix}_{r} -\begin{bmatrix}G\\k\end{bmatrix}_{r+1} =\sum_{i=1}^{r}|\mathcal B_{r,i}(G,k)|. }$$

Thus the inequality is strict if and only if some admissible $k$-block cycle partition places the newly distinguished vertex in a block with an earlier distinguished vertex. It is an equality if and only if no such partition exists.

In particular, when $k=n-1$, every graphical cycle partition consists of one edge block and $n-2$ singleton blocks. Therefore, for every distinguished set $R$,

$$|\mathcal P_{n-1}(G;R)| =|E(G)|-|E(G[R])|,$$

and the one-step difference becomes

$$\begin{bmatrix}G\\n-1\end{bmatrix}_{r} -\begin{bmatrix}G\\n-1\end{bmatrix}_{r+1} =|N_G(v_{r+1})\cap R_r|.$$

3. Equality, complete graphs, and the necessity of nesting

The conjecture's displayed weak inequalities are correct, but its accompanying description as decreasing strictly does not hold in general. Consider the connected path

$$a-b-c, \qquad v_1=a, \qquad v_2=c, \qquad k=2.$$

Its two graphical cycle partitions are

$$\bigl\{\{a,b\},\{c\}\bigr\}, \qquad \bigl\{\{a\},\{b,c\}\bigr\}.$$

Both separate $a$ from $c$, and therefore

$$\begin{bmatrix}P_3\\2\end{bmatrix}_1 = \begin{bmatrix}P_3\\2\end{bmatrix}_2 =2.$$

For complete graphs, Theorem 4.3 of the source gives

$$\mathcal C_r(K_n,x) =x^r\prod_{j=r}^{n-1}(x+j).$$

Hence

$$\mathcal C_r(K_n,x)-\mathcal C_{r+1}(K_n,x) =r x^r\prod_{j=r+1}^{n-1}(x+j).$$

Every coefficient on the right in degrees $r,\ldots,n-1$ is positive, while its degree-$n$ coefficient is zero. Thus complete graphs exhibit strict decrease at every eligible interior coefficient and equality at the singleton-partition boundary $k=n$.

Finally, the nesting stipulated in Definition 4.1 cannot be discarded. Let $G=K_{1,3}$ have center $o$ and leaves $a,b,c$, and take $k=3$. For the non-nested distinguished sets

$$R=\{o,a\}, \qquad R'=\{a,b,c\},$$

the edge-block formula gives

$$|\mathcal P_3(G;R)|=3-1=2 <3-0=3=|\mathcal P_3(G;R')|,$$

even though $|R|<|R'|$. Thus the full theorem is precisely monotonicity under inclusion of distinguished sets, and in particular under the first-$r$ labeling convention used in the conjecture.