Grafo completo de invariantes?

Question

Obviamente, gráfico invariantes son cosas maravillosas, pero los de siempre (el polinomio de Tutte, el espectro, lo que sea) no siempre puede distinguir entre nonisomorphic gráficos. De hecho, creo que incluso una combinación de los dos que he mencionado se producirá a distinguir entre dos árboles al azar del mismo tamaño, con alta probabilidad.

Hay un conocido conjunto de gráfico invariantes que no siempre distingue entre no-isomorfo gráficos? Para descartar ejemplos triviales, voy a exigir que el problema de comparar dos invariantes está en P (o, al menos, no, obviamente, equivalente a la gráfica de isomorfismo) -- así que, por ejemplo, "la matriz de adyacencia" no es una buena respuesta. (Cómputo de los invariantes se le permite ser difícil, sin embargo.)

Si esto es (como yo especie de sospecha), de hecho, abierto, ¿alguien tiene alguna idea sobre por qué debe ser duro? Un conjunto de invariantes no requieren o violar cualquier ampliamente cree que la complejidad de la teoría de las conjeturas, y en realidad no son la complejidad de la teoría de la razones para pensar que algo como lo que existe (en concreto, en virtud de derandomization, gráfico isomorfismo es en co-NP). Parece que no debería ser tan difícil...

Edit: Espinoso del comentario plantea un buen punto. Sí, no es trivialmente un grafo completo de todos los idiomas, el cual es definido por la asociación de un número entero único (o polinomio, o una etiqueta gráfico...) para cada isomorfismo clase de gráficos. Puesto que hay una contables número finito de gráficos, se puede hacer esto, y tenemos nuestra invariante.

Esto es lógicamente correcto pero no muy satisfactorio, ya que funciona para distinguir entre grupos finitos, por ejemplo, o entre finito hypergraphs o lo que sea. Así que en realidad no nos dice nada en absoluto acerca de la teoría de grafos. No estoy seguro de si puedo definir rigurosamente la noción de un "satisfacer gráfico invariante," pero aquí empieza: tiene que ser natural, en el sentido de que la computación/definición no depende de la forma arbitraria la elección de un elemento de un conjunto finito. Esto descalifica Espinoso de la solución, y creo que descalifica a Mariano, aunque puedo estar equivocado.

Answer 1

Un grafo completo invariante es computacionalmente equivalentes a un canónica de etiquetado de un gráfico. Un canónica de etiquetado es, por definición, una enumeración de los vértices de cada finito gráfico, con la propiedad de que si dos grafos son isomorfos como etiqueta gráficos, entonces todavía son isomorfos como la etiqueta de los gráficos. Si usted tiene una caja de color negro que le da un canónica de etiquetado, entonces obviamente que es un grafo completo invariante. Por otro lado, si usted tiene un grafo completo invariante para la etiqueta gráficos, entonces usted también tiene uno para parcialmente la etiqueta gráficos. Así que, dado que una caja negra que calcula el grafo completo de todos los idiomas, puede asignar la etiqueta 1 en el vértice que minimiza el invariante, a continuación, asignar una etiqueta a 2 a un segundo vértice de nuevo minimiza el invariante, y así sucesivamente.

Hay algoritmos para decidir gráfico isomorfismo para ciertos tipos de gráficos, o para todos los gráficos, pero con diferente evolución, y hay algoritmos para canónica de etiquetado, de nuevo con variables de rendimiento. Se entiende que el gráfico de isomorfismo reduce a la canónica de etiquetado, pero no necesariamente a la inversa. La distinción entre los dos problemas que se discuten en este clásico de papel por Babai y Luks.

Uno natural canónica de etiquetado de un gráfico es el que es lexicográficamente primera. Creo que lo vi, aunque no recuerdo donde, una consecuencia de que la computación este canónica de etiquetado para uno de los razonables lex órdenes en la etiqueta de los gráficos es NP-duro. Pero bien podría ser un canónica de etiquetado computable en P que no se parece en nada a la primera lex.

Como Douglas dice, nauty es un gráfico de cálculo paquete que incluye un canónica de la función de etiquetado. A menudo es muy rápido, pero no siempre. Nauty utiliza una fantasía contagiosa para colorear algoritmo. Durante mucho tiempo la gente pensaba que contagiosas para colorear algoritmos podría, en principio, resolver el canónico, el etiquetado y el gráfico de isomorfismo problemas, pero finalmente contraejemplos se encontraron en otro de los clásicos de papel por Cai, Furer, y Immerman. No estaba claro en primer lugar si este resultado negativo se podría aplicar a nauty, pero parece que no.

Answer 2

En algunas maneras, seguramente, no (suponiendo que los gráficos son infinitas). Ver MR1011177 (91f:03062) Friedman, H; Stanley, L; "Un Borel reducibilidad de la teoría de clases de estructuras contables." J. la Lógica Simbólica 54 (1989), no. 3, 894-914.

Este trabajo muestra (aunque el argumento es conciso, y al menos algunos es más antiguo folclore) que cualquier Borel (en un sentido) de la función f gráficos de asignación a cualquier otra cosa con una relación de equivalencia E en tal manera que G es isomorfo a H si f(g) E f(H) debe ser al menos tan complicado como los gráficos de sí mismos.

Para un resultado similar en grafos finitos, ver MR2135387 (2006e:03049) Calvert, Cummins, Caballero, y Miller, la Comparación de las clases de finito de estructuras. (Ruso) Álgebra Logika 43 (2004), no. 6, 666--701, 759; traducción en el Álgebra de la Lógica 43 (2004), no. 6, 374-392.

Answer 3

nauty proporciona una canónica de etiquetado de un gráfico. Aquí un enlace: http://cs.anu.edu.au/~bdm/nauty/

Answer 4

Uno puede encontrar los generadores para el anillo de invariantes de $\mathbb F_2[x\_{ij}:1\leq i < j \leq n]$ bajo la acción de $S_n$ en los índices, que son un número finito de por Noether la generación finita teorema. Creo que esto le proporciona un conjunto completo de invariantes.

Después: Como Steve observa, uno quisiera que el número de invariantes no crezca demasiado rápido. En característica cero (lo que podemos usar igual de bien), Noether seguramente nos dice que el anillo de invariantes se genera a la mayoría de los $\binom{n^2+n!}{n!}$ elementos, pero esto es bastante grande (para $n=6$ el límite 48813025503084826957958990535221725233495346780817632847728425, que es desalentador...) yo no creo que nadie sabe cómo muchos de los elementos que uno realmente necesita, sin embargo, para generar en este caso particular---generalmente de Noether unido es bastante malo.

Answer 5

La secuencia de homomorphism números de $|Hom(F_i,G)|$ para todos (isomorfismo tipos de) los gráficos de $F_i$ es un invariante de $G$ (ver Lovász, Operaciones con estructuras).

(Este ajuste a su proyecto de ley? O quieres finito invariantes sólo?)