Gráfico de Cayley - Cayley graph

El gráfico de Cayley del grupo libre en dos generadores de una y b

En matemáticas , un gráfico de Cayley , también conocido como gráfico de color de Cayley , diagrama de Cayley , diagrama de grupo o grupo de color, es un gráfico que codifica la estructura abstracta de un grupo . Su definición es sugerida por el teorema de Cayley (llamado así por Arthur Cayley ) y usa un conjunto específico de generadores para el grupo. Es una herramienta central en la teoría de grupos combinatoria y geométrica .

Definición

Sea un grupo y sea ​​un conjunto generador de . El gráfico de Cayley es un gráfico dirigido de color de borde construido de la siguiente manera: ${\ Displaystyle G}$${\ Displaystyle S}$${\ Displaystyle G}$${\ Displaystyle \ Gamma = \ Gamma (G, S)}$

• A cada elemento de se le asigna un vértice: el conjunto de vértices de se identifica con${\ Displaystyle g}$${\ Displaystyle G}$${\ Displaystyle \ Gamma}$${\ Displaystyle G.}$
• A cada elemento de se le asigna un color .${\ Displaystyle s}$${\ Displaystyle S}$${\ Displaystyle c_ {s}}$
• Para cada y , hay un borde de color dirigido desde el vértice correspondiente al correspondiente a .${\ Displaystyle g \ in G}$${\ Displaystyle s \ in S}$${\ Displaystyle c_ {s}}$${\ Displaystyle g}$${\ displaystyle gs}$

No todas las fuentes requieren que se genere el grupo. Si no es un grupo electrógeno , entonces se desconecta y cada componente conectado representa una clase lateral del subgrupo generado por . ${\ Displaystyle S}$${\ Displaystyle S}$${\ Displaystyle G}$${\ Displaystyle \ Gamma}$${\ Displaystyle S}$

Si un elemento de es su propio inverso, normalmente se representa mediante un borde no dirigido. ${\ Displaystyle s}$${\ Displaystyle S}$${\ Displaystyle s = s ^ {- 1},}$

A veces se supone que el conjunto es simétrico (es decir ) y no contiene el elemento de identidad del grupo. En este caso, el gráfico de Cayley sin color se puede representar como un gráfico simple no dirigido . ${\ Displaystyle S}$${\ Displaystyle S = S ^ {- 1}}$

En la teoría de grupos geométricos , a menudo se supone que el conjunto es finito, lo que corresponde a ser localmente finito. ${\ Displaystyle S}$${\ Displaystyle \ Gamma}$

Ejemplos de

• Suponga que es el grupo cíclico infinito y el conjunto consta del generador estándar 1 y su inverso (−1 en la notación aditiva); entonces el gráfico de Cayley es un camino infinito.${\ Displaystyle G = \ mathbb {Z}}$${\ Displaystyle S}$
• De manera similar, si es el grupo cíclico finito de orden y el conjunto consta de dos elementos, el generador estándar de y su inverso, entonces el gráfico de Cayley es el ciclo . De manera más general, los gráficos de Cayley de grupos cíclicos finitos son exactamente los gráficos circulantes .${\ Displaystyle G = \ mathbb {Z} _ {n}}$${\ Displaystyle n}$${\ Displaystyle S}$${\ Displaystyle G}$ ${\ Displaystyle C_ {n}}$
• El gráfico de Cayley del producto directo de grupos (con el producto cartesiano de los grupos electrógenos como grupo electrógeno) es el producto cartesiano de los correspondientes gráficos de Cayley. Así, el gráfico de Cayley del grupo abeliano con el conjunto de generadores que consta de cuatro elementos es la cuadrícula infinita en el plano , mientras que para el producto directo con generadores similares, el gráfico de Cayley es la cuadrícula finita en un toro .${\ Displaystyle \ mathbb {Z} ^ {2}}$${\ Displaystyle (\ pm 1,0), (0, \ pm 1)}$${\ Displaystyle \ mathbb {R} ^ {2}}$${\ Displaystyle \ mathbb {Z} _ {n} \ times \ mathbb {Z} _ {m}}$${\ Displaystyle n \ times m}$

Gráfico de Cayley del grupo diedro en dos generadores de una y b${\ Displaystyle D_ {4}}$

Gráfico de Cayley de , en dos generadores que son ambos autoinversos${\ Displaystyle D_ {4}}$

• Un gráfico de Cayley del grupo diedro en dos generadores y se muestra a la izquierda. Las flechas rojas representan la composición con . Dado que es autoinverso , las líneas azules, que representan la composición con , no están dirigidas. Por lo tanto, la gráfica es mixta: tiene ocho vértices, ocho flechas y cuatro aristas. La tabla Cayley del grupo se puede derivar de la presentación del grupo.${\ Displaystyle D_ {4}}$${\ Displaystyle a}$${\ Displaystyle b}$${\ Displaystyle a}$${\ Displaystyle b}$${\ Displaystyle b}$${\ Displaystyle D_ {4}}$

${\ Displaystyle \ langle a, b \ mid a ^ {4} = b ^ {2} = e, ab = ba ^ {3} \ rangle.}$

A la derecha se muestra una gráfica de Cayley diferente . sigue siendo el reflejo horizontal y está representado por líneas azules, y es un reflejo diagonal y está representado por líneas rosadas. Como ambos reflejos son autoinversos, el gráfico de Cayley de la derecha no está dirigido por completo. Este gráfico corresponde a la presentación${\ Displaystyle D_ {4}}$${\ Displaystyle b}$${\ Displaystyle c}$

${\ Displaystyle \ langle b, c \ mid b ^ {2} = c ^ {2} = e, bcbc = cbcb \ rangle.}$

• El gráfico de Cayley del grupo libre en dos generadores y correspondiente al conjunto se muestra en la parte superior del artículo y representa el elemento de identidad . Viajar a lo largo de un borde a la derecha representa una multiplicación por la derecha mientras que viajar a lo largo de un borde hacia arriba corresponde a la multiplicación por Dado que el grupo libre no tiene relaciones , la gráfica de Cayley no tiene ciclos . Esta gráfica de Cayley es un árbol infinito regular de 4 y es un ingrediente clave en la demostración de la paradoja de Banach-Tarski .${\ Displaystyle a}$${\ Displaystyle b}$${\ Displaystyle S = \ {a, b, a ^ {- 1}, b ^ {- 1} \}}$${\ Displaystyle e}$${\ Displaystyle a,}$${\ Displaystyle b.}$

Parte de un gráfico de Cayley del grupo de Heisenberg. (La coloración es solo para ayuda visual).

• Un gráfico de Cayley del grupo discreto de Heisenberg

${\ Displaystyle \ left \ {{\ begin {pmatrix} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \\\ end {pmatrix}}, \ x, y, z \ in \ mathbb {Z} \ right \}}$

se representa a la derecha. Los generadores usados ​​en la imagen son las tres matrices dadas por las tres permutaciones de 1, 0, 0 para las entradas . Satisfacen las relaciones , que también se pueden entender a partir de la imagen. Este es un grupo infinito no conmutativo y, a pesar de ser un espacio tridimensional, el gráfico de Cayley tiene un crecimiento de volumen en cuatro dimensiones .${\ Displaystyle X, Y, Z}$${\ Displaystyle x, y, z}$${\ Displaystyle Z = XYX ^ {- 1} Y ^ {- 1}, XZ = ZX, YZ = ZY}$

Gráfico Cayley Q8 que muestra los ciclos de multiplicación por cuaterniones i , j y k

Caracterización

El grupo actúa sobre sí mismo mediante la multiplicación por la izquierda (véase el teorema de Cayley ). Esto puede verse como la acción de en su gráfico de Cayley. Explícitamente, un elemento asigna un vértice al vértice. El conjunto de bordes del gráfico de Cayley y su color se conservan mediante esta acción: el borde se asigna al borde , y ambos tienen color . La acción de multiplicación por la izquierda de un grupo sobre sí mismo es simplemente transitiva , en particular, los gráficos de Cayley son transitivos de vértice . Lo siguiente es una especie de conversación con esto: ${\ Displaystyle G}$ ${\ Displaystyle G}$${\ Displaystyle h \ in G}$${\ Displaystyle g \ in V (\ Gamma)}$${\ Displaystyle hg \ in V (\ Gamma).}$${\ Displaystyle (g, gs)}$${\ Displaystyle (hg, hgs)}$${\ Displaystyle c_ {s}}$

Teorema de Sabidussi. Un gráfico dirigido (sin etiqueta y sin color) es un gráfico que Cayley de un grupo si y sólo si admite una acción de simplemente transitivo de por automorfismos gráfico (es decir, preservar el conjunto de aristas dirigidas)${\ Displaystyle \ Gamma}$${\ Displaystyle G}$${\ Displaystyle G}$ .

Para recuperar el grupo y el grupo electrógeno del gráfico dirigido sin etiquetar, seleccione un vértice y etiquételo por el elemento de identidad del grupo. Luego etiquete cada vértice de por el elemento único de que se asigna a El conjunto de generadores de que produce como el gráfico de Cayley es el conjunto de etiquetas de vecinos externos de . ${\ Displaystyle G}$${\ Displaystyle S}$${\ Displaystyle \ Gamma,}$${\ Displaystyle v_ {1} \ in V (\ Gamma)}$${\ Displaystyle v}$${\ Displaystyle \ Gamma}$${\ Displaystyle G}$${\ Displaystyle v_ {1}}$${\ Displaystyle v.}$${\ Displaystyle S}$${\ Displaystyle G}$${\ Displaystyle \ Gamma}$${\ Displaystyle \ Gamma (G, S)}$${\ Displaystyle v_ {1}}$

Propiedades elementales

• El gráfico de Cayley depende fundamentalmente de la elección del conjunto de generadores. Por ejemplo, si el grupo electrógeno tiene elementos, entonces cada vértice del gráfico de Cayley tiene bordes dirigidos entrantes y salientes. En el caso de un grupo electrógeno simétrico con elementos, el gráfico de Cayley es un gráfico regular dirigido de grados${\ Displaystyle \ Gamma (G, S)}$${\ Displaystyle S}$${\ Displaystyle S}$${\ Displaystyle k}$${\ Displaystyle k}$${\ Displaystyle k}$${\ Displaystyle S}$${\ Displaystyle r}$${\ Displaystyle r.}$
• Los ciclos (o paseos cerrados ) en el gráfico de Cayley indican relaciones entre los elementos de. En la construcción más elaborada del complejo de Cayley de un grupo, los caminos cerrados correspondientes a relaciones se "rellenan" con polígonos . Esto significa que el problema de construir el gráfico de Cayley de una presentación dada es equivalente a resolver el problema Palabra para .${\ Displaystyle S.}$${\ Displaystyle {\ mathcal {P}}}$${\ Displaystyle {\ mathcal {P}}}$
• Si es un homomorfismo de grupo sobreyectivo y las imágenes de los elementos del grupo electrógeno para son distintas, entonces induce una cobertura de gráficos.${\ Displaystyle f: G '\ to G}$ ${\ Displaystyle S '}$${\ Displaystyle G '}$

${\ Displaystyle {\ bar {f}}: \ Gamma (G ', S') \ a \ Gamma (G, S),}$

donde En particular, si un grupo tiene generadores, todos de orden diferente de 2, y el conjunto consta de estos generadores junto con sus inversos, entonces el gráfico de Cayley está cubierto por el árbol regular infinito de grados correspondiente al grupo libre en el mismo conjunto de generadores.${\ Displaystyle S = f (S ').}$${\ Displaystyle G}$${\ Displaystyle k}$${\ Displaystyle S}$${\ Displaystyle \ Gamma (G, S)}$${\ displaystyle 2k}$

• Para cualquier gráfico de Cayley finito, considerado no dirigido, la conectividad del vértice es al menos igual a 2/3 del grado del gráfico. Si el grupo electrógeno es mínimo (remoción de algún elemento y, si está presente, su inverso del grupo electrógeno deja un grupo que no genera), la conectividad del vértice es igual al grado. La conectividad de borde es en todos los casos igual al grado.
• Cada carácter de grupo del grupo induce un vector propio de la matriz de adyacencia de . Cuando es abeliano, el valor propio asociado es${\ Displaystyle \ chi}$${\ Displaystyle G}$${\ Displaystyle \ Gamma (G, S)}$${\ Displaystyle G}$

${\ Displaystyle \ lambda _ {\ chi} = \ sum _ {s \ in S} \ chi (s).}$

En particular, el valor propio asociado del carácter trivial (el que envía cada elemento a 1) es el grado de , es decir, el orden de . Si es un grupo abeliano, hay exactamente caracteres que determinan todos los valores propios.${\ Displaystyle \ Gamma (G, S)}$${\ Displaystyle S}$${\ Displaystyle G}$${\ Displaystyle | G |}$

Gráfico de clase lateral de Schreier

Si uno, en cambio, toma los vértices como clases laterales derechas de un subgrupo fijo, se obtiene una construcción relacionada, el gráfico de clases laterales de Schreier , que está en la base de la enumeración de clases laterales o el proceso de Todd-Coxeter . ${\ Displaystyle H,}$

Conexión con la teoría de grupos

El conocimiento sobre la estructura del grupo se puede obtener estudiando la matriz de adyacencia del gráfico y, en particular, aplicando los teoremas de la teoría de grafos espectrales .

El género de un grupo es el género mínimo para cualquier gráfico de Cayley de ese grupo.

Teoría de grupos geométricos

Para grupos infinitos, la geometría aproximada del gráfico de Cayley es fundamental para la teoría de grupos geométricos . Para un grupo generado de forma finita , esto es independiente de la elección del conjunto finito de generadores, por lo que es una propiedad intrínseca del grupo. Esto solo es interesante para los grupos infinitos: cada grupo finito es aproximadamente equivalente a un punto (o al grupo trivial), ya que se puede elegir como conjunto finito de generadores el grupo completo.

Formalmente, para una elección dada de generadores, uno tiene la palabra métrica (la distancia natural en el gráfico de Cayley), que determina un espacio métrico . La clase de equivalencia aproximada de este espacio es una invariante del grupo.

Historia

Los gráficos de Cayley fueron considerados por primera vez para grupos finitos por Arthur Cayley en 1878. Max Dehn, en sus conferencias inéditas sobre teoría de grupos de 1909–10, reintrodujo los gráficos de Cayley bajo el nombre Gruppenbild (diagrama de grupos), lo que llevó a la teoría de grupos geométricos de hoy. Su aplicación más importante fue la solución del problema verbal para el grupo fundamental de superficies con género ≥ 2, lo que equivale al problema topológico de decidir qué curvas cerradas de la superficie se contraen en un punto.

Bethe celosía

La celosía de Bethe o árbol Cayley infinito es el gráfico de Cayley del grupo libre en generadores. Una presentación de un grupo por generadores corresponde a un mapa sobreyectivo del grupo libre de generadores al grupo y al nivel de los gráficos de Cayley a un mapa del árbol de Cayley infinito al gráfico de Cayley. Esto también se puede interpretar (en topología algebraica ) como la cobertura universal del gráfico de Cayley, que en general no está simplemente conectado . ${\ Displaystyle n}$${\ Displaystyle G}$${\ Displaystyle n}$${\ Displaystyle n}$${\ Displaystyle G,}$

Ver también

• Gráfico de vértice transitivo
• Grupo electrógeno de un grupo
• Conjetura de Lovász
• Ciclos conectados por cubos
• Teoría de grafos algebraicos
• Gráfico de ciclo (álgebra)

Notas

enlaces externos

• Diagramas de Cayley
• Weisstein, Eric W. "Gráfico de Cayley" . MathWorld .