Recently, I am interested in the graph polynomial of the product of cycles.
Let $G = (V , E)$ be an undirected multi-graph with vertex set $\{1,\cdots,n\}$. The graph polynomial of $G$
is defined by
$$f\_G(x\_1,x\_2,\cdots,x\_n)=\prod\_{1\leq i<j\leq n, (i,j)\in E}(x\_i-x\_j).$$


**Conjecture:** Let $G $ be the Cartesian product graph $C\_{2n+1}\Box C\_{2m}$, then the coefficient of $x\_1^2x\_2^2\cdots x\_{(2n+1)(2m)}^2$ in the the graph polynomial $f\_G(x\_1,x\_2,\cdots, x\_{(2n+1)(2m)})$ is nonzero.


For $C\_3\Box C\_{2n}$, the conjecture is true. See [the coefficient of a special term in the expansion of the graph polynomial](https://mathoverflow.net/questions/301898/how-to-get-the-coefficient-of-a-special-term-in-the-expansion-of-the-graph-polyn)


This conjecture generalized the result about $C\_3\Box C\_{2n}$. I think it may be true. But I have no idea about the proof on the general cases.


I hope someone could give suggestions about the conjecture. I will appreciate it even if given some special cases for the conjecture such as $n=2,3$,etc.



A conjecture on the coefficient of a special term in the expansion of the graph polynomial?
The following proof is obtained jointly with Alexey Gordeev.


We start with a general


**Lemma.** Let $H=(X,E)$ be a $2d$-regular graph on the vertex set $X$, $G=H\square C\_k$ be the product of $H$ and a cycle of length $k$. Fix a field $\mathbb{F}$ and a subset $A\subset \mathbb{F}$, $|A|=d+2$. Let $\mathcal{U}$ denote the set of all proper $d$-colorings $u:X\to A$ of the vertices of $H$ with colors taken from $A$. Consider the square matrix $M$ with rows and columns indexed by the elements of $\mathcal{U}$: 
$$
M\_{u,v}=f\_H(u)\cdot \prod\_{x\in X} \frac{u(x)-v(x)}{\prod\_{b\in A\setminus u(x)} (u(x)-b)}
$$ 
for two proper colorings $u,v\in \mathcal{U}$. Here $f\_H(u)=\prod\_{(x,y)\in E} (u(y)-u(x))$ is a graph polynomial of $H$ (with somehow fixed sign.) Then 
$$
\left[\prod\_i x\_i^{d+1}\right] f\_G=\mathrm{tr}\,M^k,
$$
where the variables $x\_i$ correspond to all $k\cdot |X|$ vertices of $G$.


**Proof.** Use the [formula](https://mathoverflow.net/a/214930/4312) for the coefficient of $f\_G$:
$$
\left[\prod\_i x\_i^{d+1}\right] f\_G=\sum\_{a\_i\in A} \frac{f\_G(a\_1,\ldots)}{\prod\_i \prod\_{b\in A\setminus a\_i} (a\_i-b)} \quad \quad \quad \quad (1)
$$
The non-zero summands in the RHS of (1) correspond to proper colorings of
$G$. Any proper coloring of $G$ corresponds to a sequence $u\_1,\ldots, u\_k\in \mathcal{U}$ of the proper colorings of $H$. For such a sequence, the corresponding summand in RHS of (1) reads as
$$
M\_{u\_1,u\_2}\cdot M\_{u\_2,u\_3}\cdot \ldots \cdot M\_{u\_k,u\_1}.
$$
The sum of such products is nothing but $\mathrm{tr}\, M^k$.
In our situation $H=C\_{2n+1}$, $k=2m$ is even. We choose the field $\mathbb{F}=\mathbb{C}$ and the set $A=\{1,w,w^2\}$, where $w=e^{2\pi i/3}$. 
The reason why $\mathrm{tr}\, M^{2m}\ne 0$ is that $M$ is a non-zero antihermitian matrix. That implies that the eigenvalues of $M$ are purely imaginary and not all of them are equal to 0, that yields $(-1)^m\mathrm{tr}\, M^{2m}> 0$.
It remains to prove that $M$ is antihermitian ($M$ is certainly non-zero). That is the point why we have chosen such a set of colors.
Let $u=[u\_1,\ldots,u\_{2n+1}]\in \mathcal{U}$ be a proper 3-coloring of $C\_{2n+1}$ with 3 colors $1,w,w^2$. Denote by $u\_i^\*$ the unique element of the set $\{1,w,w^2\}\setminus \{u\_i,u\_{i-1}\}$.
Assuming that the sign of $f\_{H}$ is chosen so that $f\_H(u)=\prod\_i (u\_i-u\_{i-1})$ (the indices are cyclic modulo $2n+1$), applying the obvious relation
$$\frac1{u\_i-u\_{i}^\*}=\frac{u\_i-u\_{i-1}}
{\prod\_{b\in A\setminus u\_i} (u\_i-b)}$$
we get
$$
M\_{u,v}=\prod\_{i=1}^{2n+1}\frac{u\_i-v\_i}{u\_i-u\_i^\*}.\quad \quad (2)
$$
So the relation to check is
$$
M\_{v,u}=-\overline{M\_{u,v}}.\quad \quad \quad \quad (3)
$$
Applying (2) and substituting $\bar{z}=1/z$ for roots of unity $z=u\_i,v\_i,u\_i^\*$ we simplify (3) to the following:
$$
\prod\_i \frac{u\_i-u\_i^\*}{u\_i}=-\prod\_i \frac{v\_i^\*-v\_i}{v\_i^\*} \quad \quad (4)
$$
provided that $u\_i\ne v\_i$ for all $i$ (if $u\_i=v\_i$ for some $i$, then $M\_{u,v}=M\_{v,u}=0$).
Denote $\varepsilon\_i=u\_i/u\_{i-1}$, then $\varepsilon\_i\in \{w,w^2\}$ and $u\_i^\*=u\_i \varepsilon\_i$. Analogously write $v\_i^\*=v\_i \delta\_i$ so we rewrite (4) as
$$
\prod\_i(1-\varepsilon\_i)=-\prod\_i (1-\overline{\delta\_i})=(-1)^{1+(2n+1)}\prod \delta\_i^{-1}\prod(1-\delta\_i).
$$
Obviously $\prod \varepsilon\_i=\prod \delta\_i=1$ so this in turn rewrites as
$$
\prod\_i(1-\varepsilon\_i)=\prod\_i (1-\delta\_i). \quad \quad (5)
$$
Now we have $1-\varepsilon=\pm i\sqrt{3}\varepsilon^2$ for $\varepsilon\in \{w,w^2\}$ (the signs are distinct for $w$ and $w^2$). Substituting this for $\varepsilon\_i$'s and $\delta\_i$'s and using $\prod \delta\_i=\prod \varepsilon\_i=1$, we reduce (5) to the following fact: *the total number of $\varepsilon\_i$'s and $\delta\_i$'s which are equal to $w$ is even.* Call the index $i$ white if $u\_i=w\cdot v\_i$ and black if $u\_i=w^2\cdot v\_i$. Then $\varepsilon\_i=\delta\_i$ if $i-1,i$ have the same color and $\varepsilon\_i\ne \delta\_i$ if $i-1,i$ have different color. Obviously there are even number of indices $i$ of the second type, thus the result.


