Grafo de Cayley

En matemática el grafo de Cayley es un grafo que muestra la estructura de un grupo. Su nombre honra al matemático británico Arthur Cayley, quien introdujo estos grafos en 1878.​ Los grafos de Cayley son fundamentales en la teoría geométrica de grupos.

Grafo de Cayley del grupo libre de dos generadores, a y b.

Definición

Sea $G$ un grupo y $S\subseteq G$ un subconjunto.

El grafo de Cayley ${\mathcal {C}}$ cumple:

• los vértices del grafo ${\mathcal {C}}$ son los elementos del grupo $G$:
  $$V({\mathcal {C}})\subseteq G$$
• el par ordenado (g,h) es una arista del grafo si existe s perteneciente a S tal que gs=h:
  $$\exists s\in S:gs=h\implies (g,h)\in E({\mathcal {C}})$$
  o equivalentemente, si g^-1h pertenece a S:
  $${g^{-1}h}\in S$$

El segundo punto es en ocasiones cambiado por lo siguiente: el par ordenado (g,h) es una arista del grafo si existe s perteneciente a S tal que sg=h (o, de forma equivalente, si hg^-1 pertenece a S).

En general se estudia el grafo de Cayley con S generador del grupo G (lo que hace al grafo conexo) y tal que el neutro del grupo no está en S (de esta manera no hay lazos en el grafo). Además, suele asumirse que el conjunto S es simétrico, es decir, si t pertenece a S entonces t^-1 también. Esta última propiedad hace al grafo de Cayley no orientado.

Ejemplos

Grafo de Cayley de S₃ con conjunto de generadores {(12), (23), (13)}

Grafo de Cayley del grupo S3 con conjunto de generadores {(12), (123)}

• Si el grupo es $\mathbb {Z}$ con la operación suma y tomamos como conjunto generador a S={1} entonces el grafo de Cayley resulta un camino infinito, con aristas uniendo cada entero con su consecutivo.
• El grafo del grupo $(\mathbb {Z} _{n},+)$ con S={1,-1} es el grafo ciclo C_n.
• Si G es un grupo cualquiera con n elementos y tomamos S=G-{e} entonces su grafo de Cayley será el grafo completo K_n.
• Si A es un conjunto finito y tomamos el grupo libre F_A con $S=A\cup A^{-1}$ entonces su grafo de Cayley será un árbol infinito.​

Propiedades

• El grafo de Cayley no es independiente del conjunto de generadores que se toma. Es decir, que tomando dos generadores distintos obtenemos en general grafos no isomorfos. Vea por ejemplo las imágenes a la derecha donde se muestran dos grafos de Cayley distintos, ambos correspondientes al grupo simétrico S₃.
• Si S tiene k elementos y es simétrico (y por lo tanto el grafo es no dirigido) entonces el grafo es k-regular. Además, es transitivo en los vértices, o sea, dados dos vértices cualesquiera existe un automorfismo del grafo que lleva un vértice en el otro.​ Sin embargo, no todo grafo transitivo en vértices es el grafo de Cayley de algún grupo.​
• Un ciclo en el grafo de Cayley indica una relación no trivial en el grupo. De ahí que los únicos grafos de Cayley sin ciclos sean los de los grupos libres, siempre que el grupo no posea elementos de orden 2.​
• Si S no genera al grupo G entonces habrá varias componentes conexas del grafo, una por cada clase lateral determinada por el subgrupo generado por S.

Referencias

• Datos: Q859174
• Multimedia: Cayley graphs / Q859174