Gráfico de cayley

En matemáticas, un gráfico de Cayley, también conocido como gráfico de colores de Cayley, diagrama de Cayley, diagrama de grupo, o grupo de colores, es un gráfico que codifica la estructura abstracta de un grupo. Su definición es sugerida por el teorema de Cayley (que lleva el nombre de Arthur Cayley) y utiliza un conjunto específico de generadores para el grupo. Es una herramienta central en la teoría de grupos combinatoria y geométrica. La estructura y simetría de los gráficos de Cayley los convierte en candidatos particularmente buenos para construir familias de gráficos de expansión.

Definición

Vamos G{displaystyle G. ser un grupo y S{displaystyle S. ser un conjunto generador de G{displaystyle G.. El gráfico Cayley .. =.. ()G,S){displaystyle Gamma =Gamma (G,S)} es un gráfico dirigido a color de borde construido de la siguiente manera:

• Cada elemento g{displaystyle g} de G{displaystyle G. se asigna un vértice: el conjunto del vértice .. {displaystyle "Gamma" se identifica con G.{displaystyle G.}
• Cada elemento s{displaystyle s} de S{displaystyle S. se asigna un color cs{displaystyle C_{s}.
• Por todos g▪ ▪ G{displaystyle gin G} y s▪ ▪ S{displaystyle sin S}, hay un borde de color dirigido cs{displaystyle C_{s} del vértice correspondiente a g{displaystyle g} al correspondiente al gs{displaystyle gs}.

No todas las fuentes requieren eso S{displaystyle S. generar el grupo. Si S{displaystyle S. no es un conjunto generador para G{displaystyle G., entonces .. {displaystyle "Gamma" se desconecta y cada componente conectado representa un conjunto del subgrupo generado por S{displaystyle S..

Si un elemento s{displaystyle s} de S{displaystyle S. es su propio inverso, s=s− − 1,{displaystyle S=s^{-1},} entonces es típicamente representado por un borde no dirigido.

El set S{displaystyle S. a veces se supone que es simétrico (es decir, S=S− − 1{displaystyle S=S^{-1}) y no contiene el elemento de identidad del grupo. En este caso, el gráfico Cayley sin color puede ser representado como un simple gráfico no dirigido.

En la teoría del grupo geométrico, el conjunto S{displaystyle S. a menudo se supone que es finito que corresponde a .. {displaystyle "Gamma" ser localmente finito.

Ejemplos

• Supongamos que G=Z{displaystyle G=mathbb {Z} es el grupo cíclico infinito y el conjunto S{displaystyle S. consiste en el generador estándar 1 y su inverso (−1 en la notación aditiva); entonces el gráfico Cayley es un camino infinito.
• Del mismo modo, si G=Zn{displaystyle G=mathbb {Z} _{n} es el grupo cíclico finito de orden n{displaystyle n} y el conjunto S{displaystyle S. consta de dos elementos, el generador estándar de G{displaystyle G. y su inverso, entonces el gráfico Cayley es el ciclo Cn{displaystyle C_{n}. Más generalmente, los gráficos de Cayley de grupos cíclicos finitos son exactamente los gráficos circulantes.
• El gráfico Cayley del producto directo de grupos (con el producto cartesiano de generar conjuntos como conjunto generador) es el producto cartesiano de los correspondientes gráficos Cayley. Así el gráfico Cayley del grupo abeliano Z2{displaystyle mathbb {Z} {2}} con el conjunto de generadores que consta de cuatro elementos ()± ± 1,0),()0,± ± 1){displaystyle (pm 1,0),(0,pm 1)} es la rejilla infinita en el plano R2{displaystyle mathbb {R} {2}}, mientras que para el producto directo Zn× × Zm{displaystyle mathbb {Z} _{n}times mathbb {Z} {m} con generadores similares el gráfico Cayley es el n× × m{displaystyle ntimes m} rejilla finita en un toro.

• Un gráfico de Cayley del grupo dihedral D4{displaystyle D_{4} en dos generadores a{displaystyle a} y b{displaystyle b} se representa a la izquierda. Las flechas rojas representan la composición con a{displaystyle a}. Desde b{displaystyle b} es auto-inverso, las líneas azules, que representan la composición con b{displaystyle b}No están dirigidos. Por lo tanto el gráfico es mezclado: tiene ocho vértices, ocho flechas, y cuatro bordes. La mesa de Cayley del grupo D4{displaystyle D_{4} puede derivarse de la presentación del grupo
  .. a,b▪ ▪ a4=b2=e,ab=ba3.. .{displaystyle langle a,bmid a^{4}=b^{2}=e,ab=ba^{3}rangle.}

  
  Un gráfico diferente de Cayley D4{displaystyle D_{4} se muestra a la derecha. b{displaystyle b} es todavía la reflexión horizontal y está representada por líneas azules, y c{displaystyle c} es un reflejo diagonal y está representado por líneas rosadas. Como ambos reflejos son auto-inversos el gráfico Cayley en la derecha es completamente no dirigido. Este gráfico corresponde a la presentación
  .. b,c▪ ▪ b2=c2=e,bcbc=cbcb.. .{displaystyle langle b,cmid b^{2}=c^{2}=e,bcbc=cbrangle.}

  
• El gráfico Cayley del grupo libre en dos generadores a{displaystyle a} y b{displaystyle b} correspondiente al conjunto S={}a,b,a− − 1,b− − 1}{displaystyle S={a,b,a^{-1} se representa en la parte superior del artículo, y e{displaystyle e} representa el elemento de identidad. Viajar por un borde a la derecha representa la multiplicación correcta por a,{displaystyle a,} mientras viaja a lo largo de un borde hacia arriba corresponde a la multiplicación por b.{displaystyle b.} Dado que el grupo libre no tiene relaciones, el gráfico Cayley no tiene ciclos. Este gráfico Cayley es un árbol infinito de 4regulares y es un ingrediente clave en la prueba de la paradoja Banach-Tarski.
• Más generalmente, la celosía Bethe o el árbol de Cayley infinito es el gráfico Cayley del grupo libre en n{displaystyle n} generadores. Presentación de un grupo G{displaystyle G. por n{displaystyle n} generadores corresponde a un mapa subjetivo del grupo libre en n{displaystyle n} generadores al grupo G,{displaystyle G,} y en el nivel de los gráficos de Cayley a un mapa desde el árbol infinito de Cayley al gráfico de Cayley. Esto también puede ser interpretado (en topología algebraica) como la cubierta universal del gráfico Cayley, que no está en general simplemente conectado.

• Un gráfico de Cayley del grupo discreto Heisenberg
  {}()1xz01Sí.001),x,Sí.,z▪ ▪ Z}{displaystyle left{begin{pmatrix}1 sensiblex limitada1 demandantey limitada0 limitada1 demandante1\end{pmatrix}, x,y,zin mathbb {Z} right}

  
  se representa a la derecha. Los generadores utilizados en la imagen son los tres matrices X,Y,Z{displaystyle X,Y,Z} dado por las tres permutaciones de 1, 0, 0 para las entradas x,Sí.,z{displaystyle x,y,z}. Ellos satisfacen las relaciones Z=XYX− − 1Y− − 1,XZ=ZX,YZ=ZY{displaystyle Z=XYX^{-1}Y^{-1},XZ=ZX,YZ=ZY}, que también se puede entender de la imagen. Este es un grupo infinito no-commutante, y a pesar de ser un espacio tridimensional, el gráfico Cayley tiene un crecimiento de volumen cuatridimensional.

Caracterización

El grupo G{displaystyle G. actúa en sí misma por la multiplicación izquierda (ver el teorema de Cayley). This may be viewed as the action of G{displaystyle G. en su gráfico Cayley. Explícitamente, un elemento h▪ ▪ G{displaystyle hin G} mapas a vertex g▪ ▪ V().. ){displaystyle gin V(Gamma)} al vertex hg▪ ▪ V().. ).{displaystyle hgin V(Gamma). } El conjunto de bordes del gráfico Cayley y su color se conserva por esta acción: el borde ()g,gs){displaystyle (g,gs)} se mapea al borde ()hg,hgs){displaystyle (hg,hgs)}, ambos tienen color cs{displaystyle C_{s}. La acción de multiplicación izquierda de un grupo en sí es simplemente transitiva, en particular, los gráficos de Cayley son vertex-transitive. Lo siguiente es una especie de conversación con esto:

Para recuperar el grupo G{displaystyle G. y el conjunto generador S{displaystyle S. del gráfico dirigido no etiquetado .. ,{displaystyle Gamma} seleccionar un vértice v1▪ ▪ V().. ){displaystyle v_{1}in V(Gamma)} y etiquetarlo por el elemento de identidad del grupo. Luego etiqueta cada vértice v{displaystyle v} de .. {displaystyle "Gamma" por el elemento único G{displaystyle G. que mapas v1{displaystyle v_{1} a v.{displaystyle v.} El set S{displaystyle S. de generadores de G{displaystyle G. que rinde .. {displaystyle "Gamma" como el gráfico de Cayley .. ()G,S){displaystyle Gamma (G,S)} es el conjunto de etiquetas de vecinos v1{displaystyle v_{1}.

Propiedades elementales

• El gráfico Cayley .. ()G,S){displaystyle Gamma (G,S)} depende de una manera esencial de la elección del conjunto S{displaystyle S. de generadores. Por ejemplo, si el conjunto generador S{displaystyle S. tiene k{displaystyle k} elementos entonces cada vértice del gráfico Cayley tiene k{displaystyle k} entrando y k{displaystyle k} Saliendo de los bordes dirigidos. En el caso de un conjunto generador simétrico S{displaystyle S. con r{displaystyle r} elementos, el gráfico Cayley es un gráfico regular dirigido de grado r.{displaystyle r.}
• Ciclos (o paseos cerrados) en el gráfico Cayley indican relaciones entre los elementos S.{displaystyle S.} En la construcción más elaborada del complejo Cayley de un grupo, los caminos cerrados correspondientes a las relaciones son "llenados" por polígonos. Esto significa que el problema de construir el gráfico Cayley de una presentación dada P{displaystyle {fncipal}} es equivalente a resolver el problema de la palabra para P{displaystyle {fncipal}}.
• Si f:G.→ → G{displaystyle f:G'to G} es un grupo subjetivo homomorfismo y las imágenes de los elementos del conjunto generador S.{displaystyle S' para G.{displaystyle G. son distintos, entonces induce una cubierta de gráficos
  f̄ ̄ :.. ()G.,S.)→ → .. ()G,S),{displaystyle {bar {f}:Gamma (G',S')to Gamma (G,S),}

  
  Donde S=f()S.).{displaystyle S=f(S').} En particular, si un grupo G{displaystyle G. tiene k{displaystyle k} generadores, todo de orden diferente de 2, y el conjunto S{displaystyle S. consta de estos generadores junto con sus inversos, luego el gráfico Cayley .. ()G,S){displaystyle Gamma (G,S)} está cubierto por el infinito árbol regular de grado 2k{displaystyle 2k} correspondiente al grupo libre en el mismo conjunto de generadores.
• Para cualquier gráfico de Cayley finito, considerado como no dirigido, la conectividad del vértice es al menos igual a 2/3 del grado del gráfico. Si el conjunto de generación es mínimo (removal de cualquier elemento y, si está presente, su inversa del conjunto de generación deja un conjunto que no está generando), la conectividad del vértice es igual al grado. La conectividad del borde es en todos los casos igual al grado.
• Si *** *** reg()g)()x)=gx{displaystyle rho _{text{reg}(g)=gx} es la representación irregular izquierda con SilencioGSilencio× × SilencioGSilencio{displaystyle Новывывыхtimes matriz denotada [*** *** reg()g)]{displaystyle [rho _{text{reg}(g)}, la matriz de adyacencia .. ()G,S){displaystyle Gamma (G,S)} es A=.. s▪ ▪ S[*** *** reg()g)]{textstyle A=sum _{sin S}[rho _{text{reg}(g)}.
• Cada personaje de grupo χ χ {displaystyle chi } del grupo G{displaystyle G. induce un eigenvector de la matriz de adyacencia .. ()G,S){displaystyle Gamma (G,S)}. Cuando G{displaystyle G. es Abelian, el eigenvalue asociado es
  λ λ χ χ =.. s▪ ▪ Sχ χ ()s),{displaystyle lambda _{chi }=sum _{sin S}chi (s),}

  
  que toma la forma
  .. s▪ ▪ Se2π π ijs/SilencioGSilencio{displaystyle sum _{sin S}e^{2pi ijs/persistentes

  
  para enteros j=0,1,...... ,SilencioGSilencio− − 1.{displaystyle j=0,1,dots sobrevivirG vidas-1.} En particular, el eigenvalue asociado del carácter trivial (el que envía cada elemento a 1) es el grado de .. ()G,S){displaystyle Gamma (G,S)}, es decir, el orden S{displaystyle S.. Si G{displaystyle G. es un grupo Abeliano, hay exactamente SilencioGSilencio{displaystyle SilencioG caracteres, determinando todos los eigenvalues. La base ortonormal correspondiente de los eigenvectores es dada por vj=1SilencioGSilencio()1e2π π ij/SilencioGSilencioe2⋅ ⋅ 2π π ij/SilencioGSilencioe3⋅ ⋅ 2π π ij/SilencioGSilencio⋯ ⋯ e()SilencioGSilencio− − 1)2π π ij/SilencioGSilencio).{displaystyle v_{j}={tfrac {1}{sqrt {begin{pmatrix}1⁄2pi} ij/ vivenG habit} limite^{2cdot 2pi ij/prehensiG habit} limite^{3cdot 2pi ij/ tuyaG habit} limitcdots &e^{(Sobrevivir a una persona)2pi - Hola. Es interesante notar que este eigenbasis es independiente del conjunto generador S{displaystyle S..
  Más generalmente para grupos de generación simétricos, tomar *** *** 1,...... ,*** *** k{displaystyle rho _{1},dotsrho _{k}} un conjunto completo de representaciones irreducibles de G,{displaystyle G,} y dejar *** *** i()S)=.. s▪ ▪ S*** *** i()s){textstyle rho _{i}(S)=sum _{sin S}rho ¿Qué? con eigenvalue conjunto ▪ ▪ i()S){displaystyle Lambda _{i}(S)}. Luego el conjunto de eigenvalues de .. ()G,S){displaystyle Gamma (G,S)} es exactamente ⋃ ⋃ i▪ ▪ i()S),{textstyle bigcup Lambda... donde eigenvalue λ λ {displaystyle lambda } aparece con multiplicidad dim⁡ ⁡ ()*** *** i){displaystyle dim(rho _{i})} para cada ocurrencia de λ λ {displaystyle lambda } como un eigenvalue de *** *** i()S).{displaystyle rho _{i}(S).}

Gráfico de costura de Schreier

Si uno, en cambio, toma los vértices para ser cosets correctos de un subgrupo fijo H,{displaystyle H,} se obtiene una construcción relacionada, el gráfico Schreier coset, que se basa en la enumeración de conjuntos o en el proceso Todd-Coxeter.

Conexión con la teoría de grupos

El conocimiento sobre la estructura del grupo puede obtenerse estudiando la matriz de adyacencia del gráfico y en particular aplicando los teoremas de la teoría del gráfico espectral. Por el contrario, para conjuntos generadores simétricos, la teoría espectral y de representación .. ()G,S){displaystyle Gamma (G,S)} están directamente atados juntos: tomar *** *** 1,...... ,*** *** k{displaystyle rho _{1},dotsrho _{k}} un conjunto completo de representaciones irreducibles de G,{displaystyle G,} y dejar *** *** i()S)=.. s▪ ▪ S*** *** i()s){textstyle rho _{i}(S)=sum _{sin S}rho ¿Qué? con eigenvalues ▪ ▪ i()S){displaystyle Lambda _{i}(S)}. Luego el conjunto de eigenvalues de .. ()G,S){displaystyle Gamma (G,S)} es exactamente ⋃ ⋃ i▪ ▪ i()S),{textstyle bigcup Lambda... donde eigenvalue λ λ {displaystyle lambda } aparece con multiplicidad dim⁡ ⁡ ()*** *** i){displaystyle dim(rho _{i})} para cada ocurrencia de λ λ {displaystyle lambda } como un eigenvalue de *** *** i()S).{displaystyle rho _{i}(S).}

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 geométrica de grupos. Para un grupo finitamente generado, esto es independiente de la elección del conjunto finito de generadores, por lo que es una propiedad intrínseca del grupo. Esto sólo 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 determinada elección de generadores, se 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.

Propiedades de expansión

Cuando S=S− − 1{displaystyle S=S^{-1}, el gráfico de Cayley .. ()G,S){displaystyle Gamma (G,S)} es SilencioSSilencio{displaystyle Silencioso- técnicas regulares espectrales pueden utilizarse para analizar las propiedades de expansión del gráfico. En particular para los grupos abelianos, los eigenvalues del gráfico Cayley son más fácilmente computables y dados por λ λ χ χ =.. s▪ ▪ Sχ χ ()s){textstyle lambda _{chi }=sum _{sin S}chi (s)} con valor superior igual a SilencioSSilencio{displaystyle Silencioso, por lo que podemos utilizar la desigualdad de Cheeger para ligar la relación de expansión del borde usando la brecha espectral.

La teoría de la representación se puede utilizar para construir dichos gráficos de Cayley en expansión, en la forma de la propiedad de Kazhdan (T). Se cumple la siguiente afirmación:

Si un grupo discreto G{displaystyle G. tiene propiedad de Kazhdan (T), y S{displaystyle S. es un conjunto de generación finita y simétrica G{displaystyle G., entonces existe una constante 0}" xmlns="http://www.w3.org/1998/Math/MathML">c■0{displaystyle c]0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ba126f626d61752f62eaacaf11761a54de4dc84" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;"/> dependiendo sólo de G,S{displaystyle G,S} tal que para cualquier cociente finito Q{displaystyle Q} de G{displaystyle G. el gráfico de Cayley Q{displaystyle Q} con respecto a la imagen de S{displaystyle S. es un c{displaystyle c}- Expander.

Por ejemplo, el grupo G=SL3()Z){displaystyle G=mathrm {S} _{3}(mathbb {Z})} tiene propiedad (T) y se genera por matrices elementales y esto da ejemplos relativamente explícitos de gráficos de mayor tamaño.

Clasificación integral

Un gráfico integral es uno cuyos eigenvalues son todos enteros. Si bien la clasificación completa de los gráficos integrales sigue siendo un problema abierto, los gráficos de Cayley de ciertos grupos son siempre integrales. Utilizando caracterizaciones anteriores del espectro de gráficos Cayley, note que .. ()G,S){displaystyle Gamma (G,S)} es integral sif los eigenvalues de *** *** ()S){displaystyle rho (S)} son integrales para cada representación *** *** {displaystyle rho } de G{displaystyle G..

Grupo simple integral de Cayley

Un grupo G{displaystyle G. es Cayley integral simple (CIS) si el gráfico Cayley conectado .. ()G,S){displaystyle Gamma (G,S)} es integral exactamente cuando el conjunto generador simétrico S{displaystyle S. es el complemento de un subgrupo de G{displaystyle G.. A result of Ahmady, Bell, and Mohar shows that all CIS groups areomorphic to Z/pZ,Z/p2Z{displaystyle mathbb {Z} /pmathbb {Z}Mathbb {Z} /p^{2}mathbb {Z}, o Z2× × Z2{displaystyle mathbb {Z} _{2}times mathbb {Z} _{2} para primos p{displaystyle p}. Es importante que S{displaystyle S. en realidad genera todo el grupo G{displaystyle G. para conectar el gráfico Cayley. (Si) S{displaystyle S. no genera G{displaystyle G., el gráfico Cayley todavía puede ser integral, pero el complemento de S{displaystyle S. no es necesariamente un subgrupo.)

En el ejemplo de G=Z/5Z{displaystyle G=mathbb {Z} {Z}, los conjuntos generadores simétricos (hasta el isomorfismo gráfico) son

• S={}1,4}{displaystyle S={1,4}: .. ()G,S){displaystyle Gamma (G,S)} es un 5{displaystyle 5}- ciclo con eigenvalues 2,5− − 12,5− − 12,− − 5− − 12,− − 5− − 12{displaystyle 2,{sqrt {fn}} {fnMicroc {cH00}}} {fnMicroc {fn} {fnMicroc} {5}-1}{2}},{tfrac {-{sqrt {5}}{2}} {tfrac} {cHFF} {5}}} {2}}}}
• S={}1,2,3,4}{displaystyle S={1,2,3,4}: .. ()G,S){displaystyle Gamma (G,S)} es K5{displaystyle K_{5} con eigenvalues 4,− − 1,− − 1,− − 1,− − 1{displaystyle 4,-1,-1,-1,-1

Los únicos subgrupos de Z/5Z{displaystyle mathbb {Z} {Z} son todo el grupo y el grupo trivial, y el único conjunto generador simétrico S{displaystyle S. que produce un gráfico integral es el complemento del grupo trivial. Por lo tanto Z/5Z{displaystyle mathbb {Z} {Z} debe ser un grupo de la CEI.

La prueba de la clasificación CIS completa utiliza el hecho de que cada subgrupo e imagen homomórfica de un grupo CIS es también un grupo CIS.

Grupo integral Cayley

Una noción ligeramente diferente es la de un grupo integral Cayley G{displaystyle G., en el cual cada subconjunto simétrico S{displaystyle S. produce un gráfico integral .. ()G,S){displaystyle Gamma (G,S)}. Note que S{displaystyle S. ya no tiene que generar todo el grupo.

La lista completa de los grupos integrales de Cayley es dada por Z2n× × Z3m,Z2n× × Z4n,Q8× × Z2n,S3{displaystyle mathbb {Z} _{2}n}times mathbb {Z} _{3}^{m},mathbb {Z} _{2} {n}times mathbb {Z} _{4}{n},Q_{8}times mathbb {Z} _{2} {n}}, y el grupo de orden dicíclico 12{displaystyle 12}, donde m,n▪ ▪ Z≥ ≥ 0{displaystyle m,nin mathbb {Z} y Q8{displaystyle Q_{8} es el grupo de quaternion. La prueba se basa en dos propiedades importantes de los grupos integrales de Cayley:

• Subgrupos e imágenes homomorfas de los grupos integrales de Cayley también son grupos integrales de Cayley.
• A group is Cayley integral iff every connected Cayley graph of the group is also integral.

Grupos electrógenos normales y eulerianos

Dado un grupo general G{displaystyle G., un subconjunto S⊆ ⊆ G{displaystyle Ssubseteq G} es normal si S{displaystyle S. está cerrado bajo conjugación por elementos G{displaystyle G. (generalizando la noción de un subgrupo normal) y S{displaystyle S. es Eulerian si por cada s▪ ▪ S{displaystyle sin S}, el conjunto de elementos que generan el grupo cíclico .. s.. {displaystyle langle srangle } también figura en S{displaystyle S.. Un resultado de 2019 de Guo, Lytkina, Mazurov y Revin demuestra que el gráfico Cayley .. ()G,S){displaystyle Gamma (G,S)} es integral para cualquier subconjunto Eulerian normal S⊆ ⊆ G{displaystyle Ssubseteq G}, usando técnicas puramente teóricas de representación.

La prueba de este resultado es relativamente corta: dada S{displaystyle S. un subconjunto Eulerian normal, seleccione x1,...... ,xt▪ ▪ G{displaystyle x_{1},dotsx_{t}in G. pareja no conyugal para que S{displaystyle S. es la unión de las clases de conjugación Cl⁡ ⁡ ()xi){displaystyle operatorname {Cl} (x_{i})}. A continuación, utilizando la caracterización del espectro de un gráfico Cayley, se puede mostrar los eigenvalues de .. ()G,S){displaystyle Gamma (G,S)} son dados por {}λ λ χ χ =.. i=1tχ χ ()xi)SilencioCl⁡ ⁡ ()xi)Silencioχ χ ()1)}{textstyle left{lambda _{chi }=sum ¿Por qué? tomada sobre personajes irreducibles χ χ {displaystyle chi } de G{displaystyle G.. Cada eigenvalue λ λ χ χ {displaystyle lambda _{chi } en este conjunto debe ser un elemento Q()Especificaciones Especificaciones ){displaystyle mathbb {Q} (zeta)} para Especificaciones Especificaciones {displaystyle zeta } un primitivo mth{displaystyle m^ {th}} raíz de la unidad (donde m{displaystyle m} debe ser divisible por las órdenes de cada uno xi{displaystyle x_{i}}). Debido a que los eigenvalues son enteros algebraicos, para mostrar que son integrales basta para demostrar que son racionales, y basta con mostrar λ λ χ χ {displaystyle lambda _{chi } se fija bajo cualquier automorfismo σ σ {displaystyle sigma } de Q()Especificaciones Especificaciones ){displaystyle mathbb {Q} (zeta)}. Debe haber algunos k{displaystyle k} relativamente primo a m{displaystyle m} tales que σ σ ()χ χ ()xi))=χ χ ()xik){displaystyle sigma (chi (x_{i})=chi (x_{i}^{k})} para todos i{displaystyle i}, y porque S{displaystyle S. es tanto Eulerian como normal, σ σ ()χ χ ()xi))=χ χ ()xj){displaystyle sigma (chi (x_{i})=chi (x_{j})} para algunos j{displaystyle j}. Enviar x↦ ↦ xk{displaystyle xmapsto x^{k} clases de conjugación, así que Cl⁡ ⁡ ()xi){displaystyle operatorname {Cl} (x_{i})} y Cl⁡ ⁡ ()xj){displaystyle operatorname {Cl} (x_{j})} tienen el mismo tamaño y σ σ {displaystyle sigma } términos meramente permutados en la suma para λ λ χ χ {displaystyle lambda _{chi }. Por lo tanto λ λ χ χ {displaystyle lambda _{chi } se fija para todos los automorfismos de Q()Especificaciones Especificaciones ){displaystyle mathbb {Q} (zeta)}Así que λ λ χ χ {displaystyle lambda _{chi } es racional y por lo tanto integral.

En consecuencia, si G=An{displaystyle G=A_{n} es el grupo alternante y S{displaystyle S. es un conjunto de permutaciones dadas por {}()12i)± ± 1}{displaystyle {(12i)^{pm #, entonces el gráfico de Cayley .. ()An,S){displaystyle Gamma (A_{n},S)} es integral. (Esto resolvió un problema previamente abierto del Kourovka Notebook.) Además cuando G=Sn{displaystyle G=S_{n} es el grupo simétrico y S{displaystyle S. es el conjunto de todas las transposiciones o el conjunto de transposiciones que implican un elemento particular, el gráfico Cayley .. ()G,S){displaystyle Gamma (G,S)} es también integral.

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 de Gruppenbild (diagrama de grupos), lo que condujo a la teoría geométrica de grupos 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, que equivale al problema topológico de decidir qué curvas cerradas en la superficie se contraen hasta un punto.