# A conjecture on the coefficient of a special term in the expansion of the graph polynomial?

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

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

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.

The following proof is obtained jointly with Alexey Gordeev.

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 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.
• @Petrov Exellent work! Thanks a lot. There maybe a mistake in (4), I think it should be $$\prod_i \frac{u_i-u_i^*}{u_i^*}=-\prod_i \frac{v_i^*-v_i}{v_i} \quad \quad (4).$$ In the lemma , if $k=2m+1$ is the matrix $M$ still antihermitian matrix? Furthermore, I conjeture the corresponding cofficient of the graph polynomial of $C_{2n+1}\Box C_{2m+1}$ is zero. – Jacob.Z.Lee Jun 18 '19 at 12:54
• @Jacob.Z.Lee I think, there is no mistake, and what you write is just the same equation upto interchange of $u$ and $v$. – Fedor Petrov Jun 18 '19 at 17:21
• @Jacob.Z.Lee the matrix $M$ does not depend on $k$, it depends only on $H$. So yes, for the product of two odd cycles the coefficient is 0. But this is clear a priori: if we reverse the cyclic order in each $C_{2n+1}$, we get the same polynomial with the sign changed, thus corresponding coefficent $A$ equals to $-A$. – Fedor Petrov Jun 18 '19 at 17:44
• @Petrov More specifically， if reverse the cyclic order in $C_{2n+1}$ and $C_{2m+1}$, we get the same graph polynomial and the sigh of each $M_{u,v}$ changed. thus we get $$tr (M^{2m+1})=-tr (M^{2m+1}).$$ Hence we get the $$tr (M^{2m+1})=0.$$ Is it right? – Jacob.Z.Lee Jun 19 '19 at 1:29