Que los gráficos son de Cayley gráficos?

Question

Cada presentación del grupo determina el correspondiente grafo de Cayley, que tiene un nodo para cada elemento del grupo, y las flechas marcadas con los generadores de llegar de un elemento del grupo a otro.

Mi pregunta principal es, supongamos que tenemos un grafo dirigido Γ. ¿Cómo podemos saber si es el grafo de Cayley de un grupo de presentación?

Claramente, algunos finistic se requieren propiedades: debe estar conectado; cada vértice debe tener el mismo dentro y fuera grados; y por otra parte, la automorphism grupo de la gráfica debe ser el vértice transitiva, desde la izquierda, la acción del grupo G en el grafo de Cayley es vértice transitiva. En particular, todos los barrios de cada vértice debe ser isomorfo.

Soy consciente de Sabidussi del teorema que establece que un gráfico Γ es un grafo de Cayley de un grupo G si y sólo si se admite una acción transitiva de G mediante el gráfico de automorfismos (simplemente transitivo = exactamente un elemento de G actúa para mover un vértice v a otro w). Pero este teorema no contesta a mi pregunta, ya que se supone que ya tenemos el grupo G y la acción de G sobre Γ. El punto de mi pregunta es que se nos da sólo la gráfica Γ y buscar una gráfica de la teoría de la condición nos dice si hay o no hay un grupo G de la satisfacción de las Sabidussi condición. (En particular, no voy a ser impresionado por una respuesta que indica que Γ es un grafo de Cayley iff hay un subgrupo de G de la Automorphism grupo de Γ la satisfacción de las Sabidussi de la condición.)

Hay otras preguntas relacionadas.

• Hay no Cayley gráficos, de tal manera que todos finito subdiagramas son (inducida) subdiagramas de un grafo de Cayley? En otras palabras, esta pregunta es para preguntar si la colección de grafos de Cayley no es un conjunto cerrado en el espacio de todos los gráficos.

• Hay una computable gráfico Γ que es el grafo de Cayley de un grupo de presentación, pero que no es el grafo de Cayley de cualquier computable presentación del grupo? Aquí, por una computable gráfico me refiero a un grafo cuyos vértices son los números naturales, y cuyo borde relación es una computable relación. En el grado finito caso, uno puede construir el árbol-de-los intentos para encontrar un etiquetado de la gráfica. Este árbol es computable, infinito y finitely ramificación, así que por la Baja del teorema de la Base tendrá una baja de la rama. Por lo tanto, cada computable gráfico que es un grafo de Cayley tiene un etiquetado que es baja (en particular, estrictamente por debajo de la detención problema).

• Es posible que la cuestión de si un gráfico dado Γ es un grafo de Cayley o no depende del conjunto teórico de fondo? Por ejemplo, tal vez Γ no es un grafo de Cayley de un modelo de la teoría de conjuntos V, pero hay un forzando la extensión de V[G] en el que hay un grupo que tiene un grafo de Cayley Γ. Esto no puede ocurrir por contables de los gráficos, ya que la condición de ser un grafo de Cayley es, en el peor, Σ¹₁, pero en el caso general, es una posibilidad interesante. (Y me han confundido a mí mismo varias veces acerca de esto.)

Permítanme aclarar el tipo de respuesta que estoy buscando en mi pregunta principal.

• En el lado afirmativo, yo secretamente la esperanza de que un completamente finitistic gráfico de la condición, que si está satisfecho, significaría que la gráfica podría ser etiquetado y convertirse en un grafo de Cayley. Idealmente, este finitistic condición debe involucrar a la cuantificación de sólo más de lo finito subdiagramas de Γ, y no están relacionados con la computación cualquier infinita de objetos. Este sería genial! Tal vez no es una condición para el grado finito caso?

• En el lado negativo, me pregunto de que no puede haber tal finitistic condición. Una estrategia para demostrar esto sería mostrar que la colección de contables de Cayley gráficos no es aritméticamente definibles. Tal vez incluso no es un conjunto de Borel. De hecho, puede incluso ser un completo Σ¹₁ (analítico completo. Esto implicaría que cualquier condición de la celebración de todos y sólo los contables de Cayley gráficos debe implicar un cuantificador existencial sobre contables de objetos (por ejemplo, Γ es Cayley iff hay un etiquetado de lo que es un grafo de Cayley).

• Otra estrategia para probar la existencia de una versión más débil de un resultado negativo sería para mostrar que no son computables a los gráficos, que son grafos de Cayley, pero que no han computable de etiquetado para hacer de ellos un grafo de Cayley. Esto demostraría que la conexión entre la gráfica y el grupo de acción no puede ser tan apretado.

• Otro ataque en el lado negativo sería mostrar que el conjunto de la teoría de la dependencia se produce realmente. Lo que se necesitaría es un loco gráfico Γ, que no es un grafo de Cayley, pero de tal manera que un grupo de presentación puede ser añadido al forzar.

Answer 1

Me las he arreglado para responder a algunas de las últimas preguntas, y por favor buscar debajo de una solución en el finito de grado caso.

Teorema. Hay un incontable gráfico Γ que no es un grafo de Cayley en el conjunto de la teoría de universo V, pero que es un grafo de Cayley de un conjunto más amplio de la teoría de universo, obtenidos por forzar.

Prueba. Vamos Γ ser un grafo dirigido que es un árbol, de tal manera que todos los vértices tienen infinitas in-out grado, pero de tal forma que algunos de estos títulos son contables y algunos incontables. Por ejemplo, tal vez todos los grados son contables y de todos los grados son innumerables. No es difícil construir una gráfica. Claramente, Γ no puede ser un grafo de Cayley, ya que los grados no coinciden. Indicar el (actual) conjunto teórico universo por V, y realizar obligando a forzar la extensión de V[G] en el que Γ es el contable. (Es un hecho notable acerca de obligar a que cualquier conjunto en el que todos pueden convertirse en contable en una forzando la extensión). En la extensión de V[G], la gráfica Γ es el contable de árbol en el que cada vértice tiene countably infinito in-out grado. Por lo tanto, en el forzamiento de la extensión, Γ es el grafo de Cayley del grupo libre en countably muchos generadores.QED

Teorema. No hay un gráfico de la Γ, que no es un grafo de Cayley, pero cada finito subgrafo de Γ es parte de un grafo de Cayley. En efecto, cada contables subgrafo de Γ es parte de un grafo de Cayley. Cada contables subgrafo de Γ puede ser extendido a un mayor contables subgrafo de Γ que es un grafo de Cayley.

Prueba. El mismo gráfico Γ como por encima de las obras. Cada contables subgrafo de Γ implica sólo countably muchas aristas, y puede ser colocado en una contables subgrafo de Γ que es el grafo de Cayley del grupo libre en countably muchos generadores. QED

La conclusión es que no se puede saber si un incontable grafo es un grafo de Cayley mirando sólo lo finito subdiagramas, o, de hecho, mirando sólo a su contables subdiagramas.

Estas observaciones muestran que, en innumerables casos, uno sólo debe restringir la pregunta que al principio los gráficos de satisfacer el grado de coincidencia de la condición.

---

Permítanme también dar mayor detalles de lo finito-grado caso, siguiendo la sugerencia de François Dorais (y mi árbol-de-los intentos de argumento).

Teorema. Hay una condición en finitistic contables gráficos Γ que tiene exactamente de la finito de grados de Cayley gráficos. Específicamente, el conjunto de finito de grado contables grafos de Cayley ha complejidad en la mayoría de los Σ⁰₄ en la aritmética jerarquía.

Prueba. Supongamos que la gráfica Γ es dado a nosotros simplemente como una relación binaria en ω, es decir, un elemento de 2^wxw. La afirmación de que la gráfico está conectado ha complejidad Π⁰₂, ya que sólo debe decir que cada dos vértices están conectados por un determinado camino. El la afirmación de que la gráfica tiene finita grado y todos los in-out los grados son los mismos ha complejidad Σ⁰₄, ya que se puede decir "no es un número natural k tal que para todos los vértices v se k vértices w₁,...,w_k que apunta a v, tal que no hay otros puntos de vértice en v (y lo mismo para señalando).

Ahora, supongamos que Γ es la conexión de un grafo dirigido y todos los in-out grados k. Fijar un nodo e que le representan la identidad de grupo (si Γ es un grafo de Cayley, cualquier nodo va a hacer ya que todos ellos tienen el mismo aspecto, a fin de tomar e=0). Deje que nosotros se refieren a los k nodos apuntados a de e como el conjunto de generadores (ya que si Γ realmente es un grafo de Cayley, estos serán los generadores). Definir que p es un parcial el etiquetado de los bordes de la Γ con los generadores, si p es una función definida en un número finito de distancia de la bola de e en Γ, donde p las etiquetas de cada flecha en la pelota, con un el generador. Un etiquetado es coherente si en primer lugar, para cada nodo de cada generador se utiliza una vez que sale de eso nodo y una vez que ingresan a ese nodo, y en segundo lugar, si por cada nodo v, si hay un bucle de inicio y de fin en v, a continuación, la palabra w obtenidos a partir de que la antena funciona como un bucle desde cada nodo a sí mismo. Nosotros sólo cumplir los requisitos sobre la coherencia de p tan lejos como p es definida (pues se trata meramente de una función parcial). Por lo tanto, una coherente etiquetado es un intento de hacer un etiquetado de la gráfica en un grafo de Cayley, que no se ha ejecutado en problemas aún más.

Sea T la colección de finito coherente etiquetados, el etiquetado de todos los bordes en el primer n nodos para algunos n. Este es un finitely de ramificación del árbol de la inclusión.

Yo reclamo que Γ es un grafo de Cayley si y sólo si existen son arbitrariamente grandes coherente etiquetados. El avance la dirección es clara, puesto que podemos restringir un completo coherente etiquetado para cualquier finito subgrafo. Por el contrario, si podemos encontrar una coherente de etiquetado para cualquier finito subgrafo de Γ, entonces el árbol T es infinito y finitely de ramificación. Por lo tanto, por Konig el lema hay un infinito de la rama. Una rama las etiquetas de todos los bordes en la Γ y satisface la coherencia condición. Un etiquetado exactamente proporciona un grupo de presentación con Cayley gráfico Γ.

La complejidad de decir que cada segmento inicial de la los nodos admite una coherente etiquetado es Π⁰₂, puesto que se debe decir de cada n, existe un etiquetado de p de los n primeros nodos tales que p es coherente. Ser coherente es un Δ⁰₀ requisito en la p. QED

En particular, para reconocer cuando un grafo es un finitely generado Cayley gráfico no requieren de uno a cuantificar más de infinitos objetos, y así de finito grado gráficos, esta es una respuesta a la pregunta principal.

Me sorprendió que la parte de la descripción de conducción la complejidad es la afirmación de que los grados deben todos partido, en lugar de la afirmación de que hay coherente etiquetados en el finito subdiagramas. Esto puede ser simplificado?

Esto deja el caso de countably muchos generadores de amplio y abierto. También, este todavía no responde a la pregunta se trata de tener un computable gráfico Γ, que es una de Cayley gráfico, pero que no tiene computable presentación. Tal ejemplo, sería muy interesante. Incluso en el finito grado caso, como ya he mencionado en la pregunta, la mejor de la argumento anterior produce es una rama baja.

Answer 2

Espero que este no demasiado tangencial a contar como una "respuesta" -- como Tulia Dymarz me explicó el otro día, existen infinidad de regular finito (grado) gráficos, que no solo no son grafos de Cayley, pero no se hasta cuasi-isométrico a un grafo de Cayley! Vea el papel de Eskin, Fisher, y Whyte:

http://arxiv.org/abs/math.GR/0607207

para los ejemplos. De modo que puede haber obstrucciones a ser cuasi-isométrico a un grafo de Cayley, que puede ser añadido a tu lista de propiedades necesarias de arriba.

Answer 3

En mi interpretación de sus instrucciones, esto no es una respuesta aceptable a la pregunta, pero creo que es suficientemente diferente de lo que usted escribió a la orden de mención. También podría chispa algunas de las mejores respuestas y/o dar un mejor manejo para las preguntas de seguimiento.

El grafo dirigido Γ = (V,E) es un grafo de Cayley si y sólo si está conectado y el conjunto de borde es la unión de los gráficos de una familia de Un permutaciones de V que generan un grupo no trivial de G cuya elementos no tienen puntos fijos. (Y Γ es decir, hasta el isomorfismo, la Cayley gráfica de G para el conjunto de generadores A.)

Tenga en cuenta que cualquiera de los dos distintas permutaciones de a, b de la familia debe tener distintos gráficos, de lo contrario el trivial elemento ab^-1 de G tiene un punto fijo. Por lo tanto, la familia puede ser visto como un etiquetado de los bordes de la Γ, como en su árbol de argumento al final.

Otra forma de interpretar esta etiqueta es la siguiente. Para cada a ∈ A, cada vértice de la V tiene precisamente un borde entrante y uno saliente del borde con una etiqueta. Podemos utilizar esta etiqueta para la construcción de una acción de la libre grupo F de la_Una (con la generación de establecer Una) mediante la interpretación de cada letra de una palabra en F_Un "siga el saliente del borde de la etiqueta" y su inversa un^-1 como "siga el entrante borde de una etiqueta." Esta acción es isomorfo a la acción de un grupo sobre sí mismo si y sólo si (1) la acción es transitiva y (2) todos los vértices tienen el mismo estabilizador de R (que por ende debe ser un subgrupo normal de F_Una). Entonces Γ es el grafo de Cayley de que el cociente F_Una/R, con la generación de establecer inducida por A.

Por supuesto, esto es exactamente la etiqueta que se utiliza para su árbol de argumento al final, pero creo que vale la pena ortografía estas cosas en detalle.

Answer 4

De wikipedia : "El entramado de Bethe , donde cada nodo se une a 2n a los demás es esencialmente el grafo de Cayley de un grupo libre de n generadores." Así que la solución para Tu pregunta, al menos para los grupos con un número finito de generadores, puede ser algo likethat:

Gráfico V es un Grafo de Cayley de un grupo G si existe el gráfico B y de equivalencia de la relación de los vértices K tal que:

1. En la gráfica B se Bethe celosía y ha vértices de orden 2n ( cada vértice está conectado a 2n bordes)
2. V es isomorfo a B K ( equivalencia relación juntos pega vértices.)

Respecto a lo finito presentación de grupo y para el grupo de free parece ser natural aquí. La pregunta es ¿si el grupo tiene que tener un número infinito de generadores. Por supuesto Que os dejo no trivial parte de la prueba ;-) lo que no sé ; -), pero supongo que la relación entre Bethe Látex y grafos de Cayley parece ser el punto central aquí porque es eficaz.

---

Nota después de que Joel Comentario:

Supongamos que el fin de los bordes, que emana de ciertas vértice. Así que asignar los números 1, a primera elegido borde, 2 para el segundo y así sucesivamente hasta 2n para el último. A continuación, cada borde que emanan de ciertos vértice tendrá su número. Como en Bethe celosía cada vértice tiene la misma estructura de los bordes, se puede propagar de esta manera de realizar el pedido entre todos los vértices, por lo que cada vértice tiene la misma numeración. Entonces creo que la adecuada requisito debemos establecer en nuestra relación con los K es que debería decir algo acerca de finito ( o infinito en el caso de infinito generado grupo) de la secuencia de los bordes, pegar sólo los vértices para que la secuencia de aristas es en relación. Por ejemplo, todos los vértices conectados por secuencia (1,2,3) tiene que ser pegados ( lo que puede describir la situación en la que los generadores de $g_1,g_2,g_3$ tiene que obedecer a $g_1g_2g_3 = id$ relación ). Entonces, este tipo de relación es "global" en el sentido de que se actúa de la misma manera en cada vértice. Probablemente se puede afirmar de manera más formal:

1a. dado que es el sistema de pedidos para los bordes que emana de cada vértice

1b. relación K solo a los estados acerca de vértices conectados por finito ( o infinito) de las secuencias de los bordes ( que probablemente puede ser declarada por el requisito de que la relación K utiliza sólo el borde de las secuencias y no los nombres de los vértices)

Motivación: en cuanto a la complejidad: cada finito presentado ( o infinito presentado supongo) grupo ha infinito, forma de presentación, y también cada grupo tiene relación K para el cual G=F/K donde F es libre de grupo. Para cada grupo G puede K sea igual a la del núcleo del grupo, que es un conjunto de elementos que son iguales a la identidad. Por supuesto que puede ser de uno o varios óptimo o simples formas de presentación de grupo por medio de algún tipo de criterios de usabilidad, y por lo general K declaró puro formalmente está lejos de ser óptima. Y estoy de acuerdo, se afirma en muy extravagante. Supongo que una pregunta que requieren algunos "mínima relación K" para Bethe celosía aquí sería mucho más difícil de expresar. Cuando no se trataría de algún tipo de criterios efectivos en minimality, probablemente, que puede ser utilizado en la teoría de la presentación de los grupos, por lo que estaría lejos de la trivialidad, ya que este tipo de problemas, que yo sepa, no han solución efectiva... Pero, por supuesto, sería mucho más interesante, mientras que mi camino es probablemente cerca de trivial...

Answer 5

Conjetura: Vamos (V,E) un grafo dirigido tal que 1. El grado de cada arista es igual a los grados de cada borde y cada vértice tiene el mismo dentro y fuera grados. Luego de este grafo es un grafo de cayley. Tal vez esto no está bien, pero algunos chanchullos de estas condiciones será equivalente a tener un grafo de cayley.