Return to Answer

I am afraid this innocuous-looking question is in fact extremely hard, and I would be surprised if one could find a necessary and sufficient criterion which is more useful than the definition itself. Here is why:

The question pertains to the classical invariant theory of binary forms. Firstly, suppose your graph is $v$-regular, i.e., all vertices have the same valence $v$. Then if the $x_1,\ldots,x_n$ are interpreted as the roots of a polynomial of degree $n$, or after homogenization as a homogeneous polynomial of degree $n$ in two variables, i.e., a binary form, your sum defines an $SL_2$ invariant for such a binary form. The nonregular case likewise corresponds to what 19th century mathematicians called covariants.

Here is a fact. In the regular case, the product $nv$ has to be even since this is the number of edges. Take $n=5$ and $v$ even but not divisible by 4 such that $v<18$. Then for every graph satisfying this condition the polynomial is identically zero. Likewise you can take $v=5$ and impose $n$ even but not divisible by 4 and $n<18$ and the result also is that all graphs of this kind give zero. This is a nontrivial fact which has to do with the invariants of the binary quintic: there is no skew invariant before degree 18 which is the degree of Hermite's invariant.

Another example of your question is the following. Take $n=m^2$, and arrange the vertices into an $m\times m$ square array. Take for the graph $g$ the following: put an edge between two vertices if they are in the same row or in the same column. It is trivial to see that the polynomial will vanish if $m$ is odd. Now if you can prove that the graph polynomial is nonzero (for any even $m$) then you would have proved the Alon-Tarsi conjecture, which implies the even case of the Rota basis conjecture. As far as I know these are widely open problems.

A reference on the general graph polynomial vanishing question is: G. Sabidussi, Binary invariants and orientations of graphs, Disc. Math 101 (1992), pp. 251-277.

This very question was historically important for the development of graph theory since it motivated Petersen's work.

I am afraid this innocuous-looking question is in fact extremely hard, and I would be surprised if one could find a necessary and sufficient criterion which is more useful than the definition itself. Here is why:

The question pertains to the classical invariant theory of binary forms. Firstly, suppose your graph is $v$-regular, i.e., all vertices have the same valence $v$. Then if the $x_1,\ldots,x_n$ are interpreted as the roots of a polynomial of degree $n$, or after homogenization as a homogeneous polynomial of degree $n$ in two variables, i.e., a binary form, your sum defines an $SL_2$ invariant for such a binary form. The nonregular case likewise corresponds to what 19th century mathematicians called covariants.

Here is a fact. In the regular case, the product $nv$ has to be even since this is twice the number of edges. Take $n=5$ and $v$ even but not divisible by 4 such that $v<18$. Then for every graph satisfying this condition the polynomial is identically zero. Likewise you can take $v=5$ and impose $n$ even but not divisible by 4 and $n<18$ and the result also is that all graphs of this kind give zero. This is a nontrivial fact which has to do with the invariants of the binary quintic: there is no skew invariant before degree 18 which is the degree of Hermite's invariant.

Another example of your question is the following. Take $n=m^2$, and arrange the vertices into an $m\times m$ square array. Take for the graph $g$ the following: put an edge between two vertices if they are in the same row or in the same column. It is trivial to see that the polynomial will vanish if $m$ is odd. Now if you can prove that the graph polynomial is nonzero (for any even $m$) then you would have proved the Alon-Tarsi conjecture, which implies the even case of the Rota basis conjecture. As far as I know these are widely open problems.

A reference on the general graph polynomial vanishing question is: G. Sabidussi, Binary invariants and orientations of graphs, Disc. Math 101 (1992), pp. 251-277.

This very question was historically important for the development of graph theory since it motivated Petersen's work.

I am afraid this innocuous-looking question is in fact extremely hard, and I would be surprised if one could find a necessary and sufficient criterion which is more useful than the definition itself. Here is why:

The question pertains to the classical invariant theory of binary forms. Suppose first your graph is $v$-regular, i.e., all vertices have the same valence $v$. Then if the $x_1,\ldots,x_n$ are interpreted as the roots of a polynomial of degree $n$, or after homogenization as a homogeneous polynomial of degree $n$ in two variables, i.e., a binary form, your sum defines an $SL_2$ invariant for such a binary form. The nonregular case likewise corresponds to what 19th century mathematicians called covariants.

Here is a fact. In the regular case, the product $nv$ has to be even since this is the number of edges. Take $n=5$ and $v$ even but not divisible by 4 such that $v<18$. Then for every graph satisfying this condition the polynomial is identically zero. Likewise you can take $v=5$ and impose $n$ even but not divisible by 4 and $n<18$ and the result also is that all graphs of this kind give zero. This is a nontrivial fact which has to do with the invariants of the binary quintic: there is no skew invariant before degree 18 which is the degree of Hermite's invariant.

Another example of your question is the following. Take $n=m^2$, and arrange the vertices into an $m\times m$ square array. Take for the graph $g$ the following: put an edge between two vertices if they are in the same row or in the same column. It is trivial to see that the polynomial will vanish if $m$ is odd. Now if you can prove that the graph polynomial is nonzero (for any even $m$) then you would have proved the Alon-Tarsi conjecture, which implies the even case of the Rota basis conjecture. As far as I know these are widly open problems.

A reference on the general graph polynomial vanishing question is: G. Sabidussi, Binary invariants and orientations of graphs, Disc. Math 101 (1992), pp. 251-277.

This very question was historically important for the development of graph theory since it motivated Petersen's work.

I am afraid this innocuous-looking question is in fact extremely hard, and I would be surprised if one could find a necessary and sufficient criterion which is more useful than the definition itself. Here is why:

The question pertains to the classical invariant theory of binary forms. Firstly, suppose your graph is $v$-regular, i.e., all vertices have the same valence $v$. Then if the $x_1,\ldots,x_n$ are interpreted as the roots of a polynomial of degree $n$, or after homogenization as a homogeneous polynomial of degree $n$ in two variables, i.e., a binary form, your sum defines an $SL_2$ invariant for such a binary form. The nonregular case likewise corresponds to what 19th century mathematicians called covariants.

Here is a fact. In the regular case, the product $nv$ has to be even since this is the number of edges. Take $n=5$ and $v$ even but not divisible by 4 such that $v<18$. Then for every graph satisfying this condition the polynomial is identically zero. Likewise you can take $v=5$ and impose $n$ even but not divisible by 4 and $n<18$ and the result also is that all graphs of this kind give zero. This is a nontrivial fact which has to do with the invariants of the binary quintic: there is no skew invariant before degree 18 which is the degree of Hermite's invariant.

Another example of your question is the following. Take $n=m^2$, and arrange the vertices into an $m\times m$ square array. Take for the graph $g$ the following: put an edge between two vertices if they are in the same row or in the same column. It is trivial to see that the polynomial will vanish if $m$ is odd. Now if you can prove that the graph polynomial is nonzero (for any even $m$) then you would have proved the Alon-Tarsi conjecture, which implies the even case of the Rota basis conjecture. As far as I know these are widely open problems.

A reference on the general graph polynomial vanishing question is: G. Sabidussi, Binary invariants and orientations of graphs, Disc. Math 101 (1992), pp. 251-277.

This very question was historically important for the development of graph theory since it motivated Petersen's work.

I am afraid this innocuous-looking question is in fact extremely hard, and I would be surprised if one could find a necessary and sufficient criterion which is more useful than the definition itself. Here is why:

The question pertains to the classical invariant theory of binary forms. Suppose first your graph is $v$-regular, i.e., all vertices have the same valence $v$. Then if the $x_1,\ldots,x_n$ are interpreted as the roots of a polynomial of degree $n$, or after homogeneization as a homogeneous polynomial of degree $n$ in two variables, i.e., a binary form, your sum defines an $SL_2$ invariant for such a binary form. The nonregular case likewise corresponds to what 19th century mathematicians called covariants.

Here is a fact. In the regular case, the product $nv$ has to be even since this is the number of edges. Take $n=5$ and $v$ even but not divisible by 4 such that $v<18$. Then for every graph satisfying this condition the polynomial is identically zero. Likewise you can take $v=5$ and impose $n$ even but not divisible by 4 and $n<18$ and the result also is that all graphs of this kind give zero. This is a nontrivial fact which has to do with the invariants of the binary quintic: there is no skew invariant before degree 18 which is the degree of Hermite's invariant.

Another example of your question is the following. Take $n=m^2$, and arrange the vertices into an $m\times m$ square array. Take for the graph $g$ the following: put an edge between two vertices if they are in the same row or in the same column. It is trivial to see that the polynomial will vanish if $m$ is odd. Now if you can prove that the graph polynomial is nonzero (for any even $m$) then you would have proved the Alon-Tarsi conjecture, which implies the even case of the Rota basis conjecture. As far as I now these are wildly open problems.

A reference on the general graph polynomial vanishing question is: G. Sabidussi, Binary invariants and orientations of graphs, Disc. Math 101 (1992), pp. 251-277.

I am afraid this innocuous-looking question is in fact extremely hard, and I would be surprised if one could find a necessary and sufficient criterion which is more useful than the definition itself. Here is why:

The question pertains to the classical invariant theory of binary forms. Suppose first your graph is $v$-regular, i.e., all vertices have the same valence $v$. Then if the $x_1,\ldots,x_n$ are interpreted as the roots of a polynomial of degree $n$, or after homogenization as a homogeneous polynomial of degree $n$ in two variables, i.e., a binary form, your sum defines an $SL_2$ invariant for such a binary form. The nonregular case likewise corresponds to what 19th century mathematicians called covariants.

Here is a fact. In the regular case, the product $nv$ has to be even since this is the number of edges. Take $n=5$ and $v$ even but not divisible by 4 such that $v<18$. Then for every graph satisfying this condition the polynomial is identically zero. Likewise you can take $v=5$ and impose $n$ even but not divisible by 4 and $n<18$ and the result also is that all graphs of this kind give zero. This is a nontrivial fact which has to do with the invariants of the binary quintic: there is no skew invariant before degree 18 which is the degree of Hermite's invariant.

Another example of your question is the following. Take $n=m^2$, and arrange the vertices into an $m\times m$ square array. Take for the graph $g$ the following: put an edge between two vertices if they are in the same row or in the same column. It is trivial to see that the polynomial will vanish if $m$ is odd. Now if you can prove that the graph polynomial is nonzero (for any even $m$) then you would have proved the Alon-Tarsi conjecture, which implies the even case of the Rota basis conjecture. As far as I know these are widly open problems.

A reference on the general graph polynomial vanishing question is: G. Sabidussi, Binary invariants and orientations of graphs, Disc. Math 101 (1992), pp. 251-277.

This very question was historically important for the development of graph theory since it motivated Petersen's work.