En matemáticas , un gráfico de Cayley , también conocido como un gráfico de Cayley de color , diagrama de Cayley , diagrama de grupo , o grupo de color [1] 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, generalmente finito, de generadores para el grupo. Es una herramienta central en la teoría de grupos combinatoria y geométrica .
Familias de gráficos definidas por sus automorfismos | ||||
---|---|---|---|---|
distancia-transitiva | → | distancia regular | ← | muy regular |
↓ | ||||
simétrico (arco-transitivo) | ← | t -transitivo, t ≥ 2 | simétrico sesgado | |
↓ | ||||
(si está conectado) vértice y borde transitivo | → | edge-transititive y regular | → | borde transitivo |
↓ | ↓ | ↓ | ||
vértice-transitivo | → | regular | → | (si es bipartito) birregular |
↑ | ||||
Gráfico de Cayley | ← | simétrico cero | asimétrico |
Definición
Suponer que es un grupo yes un conjunto generador de. El gráfico de Cayleyes un gráfico dirigido a color construido de la siguiente manera: [2]
- Cada elemento de se le asigna un vértice: el conjunto de vértices de se identifica con
- Cada generador de se le asigna un color .
- Para cualquier y los vértices correspondientes a los elementos y están unidos por un borde de color dirigido Así, el borde se puso consta de pares de la forma con proporcionando el color.
En la teoría de grupos geométricos , el conjuntogeneralmente se asume que es finito, simétrico (es decir,) y no contienen el elemento de identidad del grupo. En este caso, el gráfico Cayley sin color es un gráfico ordinario : sus bordes no están orientados y no contiene bucles ( ciclos de un solo elemento).
Ejemplos de
- Suponer 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.
- Del mismo modo, si es el grupo cíclico finito de orden y el set 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 .
- 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. [3] 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 avión, mientras que para el producto directo con generadores similares, el gráfico de Cayley es el cuadrícula finita en un toro .
- Una gráfica de Cayley del grupo diedro en dos generadores y se representa a la izquierda. Las flechas rojas representan la composición con. Desdees autoinverso , las líneas azules, que representan la composición con, no están dirigidos. Por tanto, la gráfica es mixta: tiene ocho vértices, ocho flechas y cuatro aristas. La mesa Cayley del grupose puede derivar de la presentación grupal
- Un gráfico de Cayley diferente de se muestra a la derecha. 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
- 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 la multiplicación a la derecha mientras viaja a lo largo de un borde hacia arriba corresponde a la multiplicación por Dado que el grupo libre no tiene relaciones , el gráfico 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 .
- Un gráfico de Cayley del grupo discreto de Heisenberg
- se representa a la derecha. Los generadores utilizados en la imagen son las tres matrices dado por las tres permutaciones de 1, 0, 0 para las entradas . Satisfacen las relaciones , que también se puede entender en 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 . [ cita requerida ]
Caracterización
El grupo actúa sobre sí mismo mediante multiplicación por la izquierda (véase el teorema de Cayley ). Esto puede verse como la acción deen su gráfico de Cayley. Explícitamente, un elemento mapea un vértice al vértice El conjunto de bordes dentro del gráfico de Cayley se conserva mediante esta acción: el borde se transforma en el borde . La acción de multiplicación por la izquierda de cualquier grupo sobre sí mismo es simplemente transitiva , en particular, el gráfico de Cayley es transitivo de vértice . Esto conduce a la siguiente caracterización de los gráficos de Cayley:
- Teorema de Sabidussi. Un gráfico es una gráfica de Cayley de un grupo si y sólo si admite una acción simplemente transitiva de por automorfismos gráficos (es decir, preservando el conjunto de aristas) . [4]
Para recuperar el grupo y el grupo electrógeno del gráfico de Cayley seleccionar un vértice y etiquetarlo por el elemento de identidad del grupo. Luego etiqueta cada vértice de por el elemento único de que transforma dentro El conjunto de generadores de que cede ya que el gráfico de Cayley es el conjunto de etiquetas de los vértices adyacentes al vértice seleccionado. El grupo electrógeno es finito (esta es una suposición común para los gráficos de Cayley) si y solo si el gráfico es localmente finito (es decir, cada vértice es adyacente a un número finito de aristas).
Propiedades elementales
- Si un miembro del grupo electrógeno es su propia inversa, entonces se representa típicamente por un borde no dirigido.
- El gráfico de Cayley depende de manera esencial de la elección del conjunto de generadores. Por ejemplo, si el grupo electrógeno posee elementos, entonces cada vértice del gráfico de Cayley tiene entrante y bordes dirigidos 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
- Los ciclos (o paseos cerrados ) en el gráfico de Cayley indican relaciones entre los elementos deEn la construcción más elaborada del complejo de Cayley de un grupo, los caminos cerrados correspondientes a las relaciones se "rellenan" con polígonos . Esto significa que el problema de construir el gráfico de Cayley de una presentación dadaes equivalente a resolver el problema verbal para. [1]
- Si es un homomorfismo de grupo sobreyectivo y las imágenes de los elementos del grupo electrógeno por son distintos, entonces induce una cobertura de gráficos
- dónde En particular, si un grupo posee generadores, todos de orden diferente a 2, y el conjunto consta de estos generadores junto con sus inversos, entonces el gráfico de Cayley está cubierto por el infinito árbol regular de grado correspondiente al grupo libre en el mismo conjunto de generadores.
- Un gráfico se puede construir incluso si el conjunto no genera el grupo Sin embargo, está desconectado y no se considera un gráfico de Cayley. En este caso, cada componente conectado del gráfico representa una clase lateral del subgrupo generado por
- 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. [5]
- Cada personaje del grupo del grupo induce un vector propio de la matriz de adyacencia de. Cuándoes abeliano, el valor propio asociado es
- 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, determinando todos los valores propios.
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 .
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. [6]
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 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
Las gráficas de Cayley fueron consideradas por primera vez para grupos finitos por Arthur Cayley en 1878. [2] Max Dehn en sus conferencias inéditas sobre teoría de grupos de 1909-10 reintrodujo las gráficas de Cayley bajo el nombre Gruppenbild (diagrama de grupos), lo que llevó a la teoría de grupos geométricos 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. [7]
Bethe celosía
La celosía de Bethe o árbol Cayley infinito es el gráfico de Cayley del grupo libre engeneradores. Una presentación de un grupo por generadores corresponde a un mapa sobreyectivo del grupo libre en generadores al grupo y al nivel de los gráficos de Cayley a un mapa desde el á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 .
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
- ^ a b Magnus, Wilhelm ; Karrass, Abraham; Solitar, Donald (2004) [1966]. Teoría combinatoria de grupos: presentaciones de grupos en términos de generadores y relaciones . Mensajero. ISBN 978-0-486-43830-6.
- ^ a b Cayley, Arthur (1878). "Desiderata y sugerencias: No. 2. La Teoría de grupos: representación gráfica" . Revista Estadounidense de Matemáticas . 1 (2): 174–6. doi : 10.2307 / 2369306 . JSTOR 2369306 . En sus Collected Mathematical Papers 10: 403–405.
- ^ Theron, Daniel Peter (1988), Una extensión del concepto de representaciones gráficamente regulares , Ph.D. tesis, Universidad de Wisconsin, Madison, pág. 46, MR 2636729.
- ^ Sabidussi, Gert (octubre de 1958). "En una clase de gráficos libres de puntos fijos" . Actas de la American Mathematical Society . 9 (5): 800–4. doi : 10.1090 / s0002-9939-1958-0097068-7 . JSTOR 2033090 .
- ^ Ver teorema 3.7 de Babai, László (1995). "27. Grupos de automorfismo, isomorfismo, reconstrucción" (PDF) . En Graham, Ronald L .; Grötschel, Martin ; Lovász, László (eds.). Manual de combinatoria . 1 . Elsevier. págs. 1447-1540. ISBN 9780444823465.
- ^ White, Arthur T. (1972). "Sobre el género de un grupo" . Transacciones de la American Mathematical Society . 173 : 203–214. doi : 10.1090 / S0002-9947-1972-0317980-2 . Señor 0317980 .
- ^ Dehn, Max (2012) [1987]. Artículos sobre topología y teoría de grupos . Springer-Verlag. ISBN 1461291070.Traducido del alemán y con introducciones y un apéndice de John Stillwell , y con un apéndice de Otto Schreier .
enlaces externos
- Diagramas de Cayley
- Weisstein, Eric W. "Gráfico de Cayley" . MathWorld .