The recursive profile conjecture for distance games on complete bipartite graphs

Complete bivariate profiles and the conjectured recurrence for Col and Snort

Svenja Huntemann and Lexi A. Nash formulate Conjecture 1 in their published paper The Polynomial Profile of Distance Games on Paths and Cycles, INTEGERS 22 (2022), Article G4. For the complete bipartite graph $K_{m,n}$, their conjecture concerns the numbers of legal positions in Col and Snort, with an inhomogeneous recurrence whose constants are identified with OEIS A260217. The paper defines a profile by counting legal positions without assuming alternating play. We prove the conjecture for every $m,n$ and, more strongly, determine the full bivariate polynomial profiles of both games.

Let $U$ and $V$ denote the bipartition classes, with $|U|=m$ and $|V|=n$. Every vertex is either unoccupied, blue, or red. Give a position with $b$ blue vertices and $r$ red vertices the weight $x^b y^r$, and write $P^{\mathrm{Col}}_{m,n}(x,y)$ and $P^{\mathrm{Snort}}_{m,n}(x,y)$ for the sums of these weights over the legal positions. Set

$$A=1+x+y,\qquad B=1+x,\qquad C=1+y. \tag{1}$$

In Col, adjacent vertices cannot have the same color. In Snort, adjacent vertices cannot have opposite colors.

1. Exact bivariate Col profile. Classify a legal position according to the set of colors appearing in $U$.

• If $U$ is entirely unoccupied, the vertices of $V$ can be colored independently, contributing $A^n$.
• If blue is the unique color appearing in $U$, the nonempty blue subset contributes $B^m-1$, and each vertex of $V$ is either unoccupied or red. The contribution is $(B^m-1)C^n$.
• If red is the unique color appearing in $U$, the contribution is $(C^m-1)B^n$.
• If both colors appear in $U$, every vertex of $V$ must be unoccupied. Inclusion-exclusion gives the contribution $A^m-B^m-C^m+1$.

These four cases are disjoint and exhaustive. Therefore

$$P^{\mathrm{Col}}_{m,n}(x,y) =A^n+(B^m-1)C^n+(C^m-1)B^n +A^m-B^m-C^m+1. \tag{2}$$

Equivalently, in symmetric form,

$$P^{\mathrm{Col}}_{m,n}(x,y) =A^m+A^n+B^mC^n+C^mB^n -B^m-C^m-B^n-C^n+1. \tag{3}$$

The argument includes the degenerate cases $m=0$ or $n=0$.

2. Exact bivariate Snort profile. The same four-way classification applies. If only blue appears in $U$, vertices of $V$ may be blue or unoccupied, contributing $(B^m-1)B^n$. If only red appears in $U$, the corresponding contribution is $(C^m-1)C^n$. The empty and two-color cases are unchanged. Consequently,

$$P^{\mathrm{Snort}}_{m,n}(x,y) =A^n+(B^m-1)B^n+(C^m-1)C^n +A^m-B^m-C^m+1. \tag{4}$$

Thus

$$P^{\mathrm{Snort}}_{m,n}(x,y) =A^m+A^n+B^{m+n}+C^{m+n} -B^m-C^m-B^n-C^n+1. \tag{5}$$

In general, (3) and (5) are different bivariate polynomials. However, putting $x=y=t$ makes $B=C=1+t$, so both become the same univariate position polynomial:

$$P_{m,n}(t) =(1+2t)^m+(1+2t)^n+2(1+t)^{m+n} -2(1+t)^m-2(1+t)^n+1. \tag{6}$$

This equality also agrees with the known bipartite Col--Snort profile equivalence recalled in the source paper: interchanging blue and red on one bipartition class converts one legality rule into the other while preserving the total number of occupied vertices. It need not preserve the separate color counts, explaining the distinction between (3) and (5).

3. Complete enumeration and the conjectured recurrence. Evaluating (6) at $t=1$ gives, for all $m,n\geq 0$,

$$F_{m,n}=P_{m,n}(1) =3^m+3^n+2^{m+n+1}-2^{m+1}-2^{n+1}+1. \tag{7}$$

For example,

$$F_{1,1}=7,\qquad F_{2,2}=35,\qquad F_{2,3}=77, \qquad F_{3,3}=151,\qquad F_{4,4}=611. \tag{8}$$

For fixed $m$, rearrange (7) as

$$F_{m,n}=3^n+2(2^m-1)2^n+D_m, \qquad D_m=3^m-2^{m+1}+1. \tag{9}$$

The operator $f_n\mapsto f_n-5f_{n-1}+6f_{n-2}$ annihilates both $3^n$ and $2^n$, and sends the constant $D_m$ to $2D_m$. Hence, for every $m\geq 0$ and $n\geq 2$,

$$F_{m,n}=5F_{m,n-1}-6F_{m,n-2}+c_m, \tag{10}$$

where

$$c_m=2D_m=2\cdot 3^m-2^{m+2}+2. \tag{11}$$

The first nonzero constants are precisely

$$c_2=4,\qquad c_3=24,\qquad c_4=100, \qquad c_5=360,\qquad c_6=1204. \tag{12}$$

The preexisting OEIS formula is $a(j)=2\cdot 3^{j-1}-2^{j+1}+2$. Its correct index shift in the conjecture is therefore

$$c_m=a(m+1)=\mathrm{A260217}(m+1). \tag{13}$$

The closed form also supplies the initial conditions

$$F_{m,0}=3^m,\qquad F_{m,1}=3^m+2^{m+1}. \tag{14}$$

Thus (10)--(14) establish every coefficient and initial condition in Conjecture 1, with no restriction on the sizes of the two bipartition classes.

4. Stronger polynomial recurrence and generating function. The same argument works before specialization. Let

$$a=1+2t,\qquad b=1+t,\qquad D_m(t)=a^m-2b^m+1. \tag{15}$$

Equation (6) becomes

$$P_{m,n}(t)=a^n+2(b^m-1)b^n+D_m(t). \tag{16}$$

Since $(1-a)(1-b)=2t^2$, it follows that, for $n\geq 2$,

$$P_{m,n}(t) =(2+3t)P_{m,n-1}(t) -(1+3t+2t^2)P_{m,n-2}(t) +2t^2\bigl((1+2t)^m-2(1+t)^m+1\bigr). \tag{17}$$

Moreover, the entire fixed-$m$ profile sequence has the explicit ordinary generating function

$$\sum_{n\geq 0}P_{m,n}(t)z^n =\frac{1}{1-(1+2t)z} +\frac{2((1+t)^m-1)}{1-(1+t)z} +\frac{(1+2t)^m-2(1+t)^m+1}{1-z}. \tag{18}$$

In particular, the conjectured numerical recurrence is the specialization $t=1$ of the stronger complete polynomial identity (17), while (3) and (5) determine the separate two-color profiles themselves.