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


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

  • $\begingroup$ Interesting question. I'd be interested to learn what led you to this question. $\endgroup$ – Jim Conant Feb 25 '11 at 15:06
  • $\begingroup$ You have a misprint in your polynomial, right? It must be $P_{g}(x_{1}, \cdots,x_{n})$ $\endgroup$ – Pedro Martins Rodrigues Feb 25 '11 at 15:15
  • 1
    $\begingroup$ The road to this question is not that long actually: all symmetric and translation-invariant polynomials are linear combinations of (a subset of) polynomials obtained from multigraphs. For example discriminants. As it turns out that about half of the graphs yield the zero polynomial, it was a natural question... $\endgroup$ – Per Alexandersson Feb 25 '11 at 16:55
  • 3
    $\begingroup$ see this paper arxiv.org/abs/1104.0589 for a recent line of research involving these graph polynomials $\endgroup$ – Abdelmalek Abdesselam May 1 '11 at 18:18

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.

  • 1
    $\begingroup$ Thanks! I suspected that the problem was indeed very hard, since there was abolutely no pattern in the graphs I have found that dies. $\endgroup$ – Per Alexandersson Feb 25 '11 at 22:14

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.