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

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.

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 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.

| cite | improve this answer | |
  • $\begingroup$ @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. $\endgroup$ – Jacob.Z.Lee Jun 18 '19 at 12:54
  • $\begingroup$ @Jacob.Z.Lee I think, there is no mistake, and what you write is just the same equation upto interchange of $u$ and $v$. $\endgroup$ – Fedor Petrov Jun 18 '19 at 17:21
  • $\begingroup$ @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$. $\endgroup$ – Fedor Petrov Jun 18 '19 at 17:44
  • $\begingroup$ @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? $\endgroup$ – Jacob.Z.Lee Jun 19 '19 at 1:29
  • $\begingroup$ @Jacob.Z.Lee You do not even need to use that the coefficient is the trace here. It vanishes by its own right. $\endgroup$ – Fedor Petrov Jun 19 '19 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.