Symmetric polynomial from graphs

Question

Let $g$ be a directed, connected multigraph, on $n$ vertices, without loops.

Define

$$P_g(x_1,\dots,x_n) := Sym\left[ \prod_{(i,j) \in g} (x_i-x_j) \right]$$

where $(i,j)$ is the directed edge from $i$ to $j,$ and $Sym$ denotes the symmetrization, that is, sum of all permutations of variables in the argument.

Now, for some multigraphs $g,$ we have that $P_g$ is identically zero.

A sufficient condition is that if we can change the direction of an odd number of edges in $g$ and obtain a graph isomorphic to $g,$ then $P_g$ is identically 0.

This is however not necessary, as the graph with edges (1,2),(2,3),(3,4),(2,4),(2,4) will give a polynomial that is identically 0.

The number of connected multigraphs with n edges that yields a zero polynomial are, for n=1,..,6, equal to 1,0,3,2,19,20, and this sequence gives no hits in Sloane.

What I am asking for is a necessary and sufficient condition of a graph that gives the zero polynomial, as defined by the procedure above.

EDIT: Note that if $g_1$ and $g_2$ are isomorphic as undirected graphs, then $P_{g_1} = \pm P_{g_2}.$ Changing the direction of one single edge changes the sign of the associated polynomial.

Answer 1

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.