Simétrica polinomio de gráficos

Question

Deje $g$ ser dirigido, conectado multigraph, en $n$ vértices, sin bucles.

Definir

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

donde $(i,j)$ es la dirigida borde de $i$ a $j,$ e $Sym$ denota la simetrización, es decir, la suma de todas las permutaciones de las variables en el argumento.

Ahora, para algunos multigraphs $g,$ tenemos que $P_g$ es idéntica a cero.

Una condición suficiente es que si podemos cambiar la dirección de un número impar de aristas en $g$ y obtener un grafo isomorfo a $g,$ entonces $P_g$ es idéntica 0.

Sin embargo, esto no es necesario, como en el gráfico con los bordes (1,2),(2,3),(3,4),(2,4),(2,4) le dará un polinomio que es idéntica a 0.

El número de conectados multigraphs con n aristas que se obtiene un cero del polinomio son, para n=1,..,6, equivalente a 1,0,3,2,19,20, y esta secuencia no da golpes en Sloane.

Lo que estoy pidiendo es una condición necesaria y suficiente de un gráfico que da el polinomio cero, tal como se define por el procedimiento anterior.

EDIT: tenga en cuenta que si $g_1$ e $g_2$ son isomorfos como grafo gráficos, a continuación, $P_{g_1} = \pm P_{g_2}.$ Cambiar la dirección de un solo filo cambia el signo del polinomio asociado.

Answer 1

Me temo que este aparentemente inofensivos que la pregunta en realidad es extremadamente duro, y me sorprendería si se podía encontrar a un necesario y suficiente criterio de que es más útil que la propia definición. Aquí es por qué:

La pregunta se refiere a la clásica teoría de invariantes de forma binaria. En primer lugar, supongamos que su gráfica es $v$-regular, es decir, todos los nodos tienen la misma valencia $v$. Entonces, si el $x_1,\ldots,x_n$ se interpretan como las raíces de un polinomio de grado $n$, o después de la homogeneización como un polinomio homogéneo de grado $n$ en dos variables, es decir, una forma binaria, su suma se define una $SL_2$ invariante para una forma binaria. El nonregular caso, asimismo, corresponde a lo que es del siglo 19 matemáticos llamados covariants.

Aquí es un hecho. En el caso habitual, el producto $nv$ tiene que ser, incluso, ya que esta es el doble de la número de aristas. Tome $n=5$ e $v$ incluso pero no divisible por 4 tal que $v<18$. A continuación, para cada gráfico de la satisfacción de esta condición el polinomio es idéntica a cero. Del mismo modo que usted puede tomar $v=5$ e imponer $n$ incluso pero no divisible por 4 y $n<18$ y el resultado también es que todos los gráficos de este tipo de cero. Este es un hecho trivial que tiene que ver con los invariantes de los binarios de quintic: no hay ningún sesgo invariante antes de grado 18, en la que se el grado de Hermite invariable.

Otro ejemplo de la pregunta es la siguiente. Tome $n=m^2$, y organizar los vértices en una $m\times m$ matriz cuadrada. Para que la gráfica de $g$ el siguiente: poner una arista entre dos vértices si están en la misma fila o en la misma columna. Es trivial ver que el polinomio se desvanecerá si $m$ es impar. Ahora bien, si usted puede demostrar que la gráfica polinomio es distinto de cero (para cualquiera incluso $m$) a continuación, se hubiera demostrado el Alon-Tarsi conjetura, lo que implica, incluso, caso de de la base Rota conjetura. Que yo sepa estos son ampliamente los problemas abiertos.

Una referencia en el gráfico general polinomio de fuga pregunta es: G. Sabidussi, Binario invariantes y orientaciones de los gráficos, de Disco. Matemáticas 101 (1992), pp 251-277.

Esta cuestión ha sido históricamente importante para el desarrollo de la teoría de grafos, ya que motivado Petersen trabajo.