gráfico de cayley

Gráfico definido a partir de un grupo matemático.

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

En matemáticas , un gráfico de Cayley , también conocido como gráfico de colores de Cayley , diagrama de Cayley , diagrama de grupos o grupo de colores , ^[1] 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 combinatoria y geométrica de grupos . La estructura y simetría de los gráficos de Cayley los convierte en candidatos particularmente buenos para construir gráficos de expansión .

Definición

Sea un grupo y sea un conjunto generador de . El gráfico de Cayley es un gráfico dirigido con bordes coloreados construido de la siguiente manera: ^[2] ${\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 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 toda convención exige que se genere el grupo. Si no es un grupo electrógeno para , entonces está desconectado 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 propia inversa, normalmente se representa mediante una arista no dirigida. ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle s=s^{-1},}$

A menudo se supone que el conjunto es finito, especialmente en la teoría geométrica de grupos , lo que corresponde a ser localmente finito y estar generado de forma finita. ${\displaystyle S}$ ${\displaystyle \Gamma }$ ${\displaystyle G}$

A veces se supone que el conjunto es simétrico ( ) y que 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}}$

Ejemplos

• Supongamos 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, las gráficas de Cayley de grupos cíclicos finitos son exactamente las gráficas 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 grupos electrógenos como grupo electrógeno) es el producto cartesiano de los gráficos de Cayley correspondientes. ^[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 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 diédrico en dos generadores a y b ${\displaystyle D_{4}}$

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

• A la izquierda se muestra un gráfico de Cayley del grupo diédrico en dos generadores . Las flechas rojas representan la composición con . Como es autoinverso , las líneas azules, que representan la composición con , no están dirigidas. Por tanto el gráfico es mixto: 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 un gráfico 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 ambas reflexiones son autoinversas, el gráfico de Cayley de la derecha no está dirigido en absoluto. 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, siendo la identidad. Viajar a lo largo de un borde hacia la derecha representa la multiplicación por la derecha mientras que viajar a lo largo de un borde hacia arriba corresponde a la multiplicación por Como el grupo libre no tiene relaciones , el gráfico de Cayley no tiene ciclos : es el árbol infinito de 4 regulares . Es un ingrediente clave en la prueba de la paradoja de Banach-Tarski . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle S=\{a,b,a^{-1},b^{-1}\}}$ ${\displaystyle e}$ ${\displaystyle a,}$ ${\displaystyle b.}$
• De manera más general, la red de Bethe o árbol de Cayley es el gráfico de Cayley del grupo libre de generadores. Una presentación de un grupo por generadores corresponde a un homomorfismo sobreyectivo del grupo libre en generadores al grupo que define un mapa desde el árbol de Cayley al gráfico de Cayley de . Al interpretar los gráficos topológicamente como complejos simpliciales unidimensionales , el árbol infinito simplemente conexo es la cobertura universal del gráfico de Cayley; y el núcleo del mapeo es el grupo fundamental del gráfico de Cayley. ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle G,}$ ${\displaystyle G}$

Parte de un gráfico de Cayley del grupo Heisenberg. (El coloreado es sólo como 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 utilizados 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 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 de cuatro dimensiones . ^{[ cita necesaria ]} ${\displaystyle X,Y,Z}$ ${\displaystyle x,y,z}$ ${\displaystyle Z=XYX^{-1}Y^{-1},XZ=ZX,YZ=ZY}$

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

Caracterización

El grupo actúa sobre sí mismo mediante multiplicación por la izquierda (ver 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 aristas del gráfico de Cayley y su color se conservan mediante esta acción: la arista se asigna a la arista , y ambas tienen color . De hecho, todos los automorfismos del grafo dirigido coloreado son de esta forma, por lo que es isomorfo al grupo de simetría de . ^{[nota 1] [nota 2]} ${\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}}$ ${\displaystyle \Gamma }$ ${\displaystyle G}$ ${\displaystyle \Gamma }$

La acción de multiplicación por la izquierda de un grupo sobre sí mismo es simplemente transitiva , en particular, las gráficas de Cayley son transitivas de vértice . Lo siguiente es una especie de recíproco de esto:

Teorema de Sabidussi  :  un gráfico dirigido (sin etiquetar ni colorear) es un gráfico de Cayley de un grupo si y sólo si admite una acción simplemente transitiva de automorfismos del gráfico (es decir, preservando el conjunto de aristas dirigidas). ^[4] ${\displaystyle \Gamma }$ ${\displaystyle G}$ ${\displaystyle G}$

Para recuperar el grupo y el grupo electrógeno del grafo 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 . Dado que no está coloreado, podría tener más automorfismos de gráficos dirigidos que los mapas de multiplicación de la izquierda, por ejemplo, automorfismos de grupo de los cuales permuta . ${\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}}$ ${\displaystyle \Gamma }$ ${\displaystyle G}$ ${\displaystyle S}$

Propiedades elementales

• El gráfico de Cayley depende de manera esencial de la elección del conjunto de generadores. Por ejemplo, si el conjunto generador tiene elementos, entonces cada vértice del gráfico de Cayley tiene aristas dirigidas entrantes y salientes. En el caso de un grupo electrógeno simétrico con elementos, el gráfico de Cayley es un gráfico dirigido regular de grado ${\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 las relaciones se "rellenan" con polígonos . Esto significa que el problema de construir la gráfica de Cayley de una presentación determinada equivale a resolver el problema verbal de . ^[1] ${\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 son distintas, entonces induce una cobertura de gráficos. ${\displaystyle f:G'\to G}$ ${\displaystyle S'}$ ${\displaystyle G'}$
  $${\displaystyle {\bar {f}}:\Gamma (G',S')\to \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 grado 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 de los vértices es al menos igual a 2/3 del grado del gráfico. Si el conjunto generador es mínimo (la eliminación de cualquier elemento y, si está presente, su inverso del conjunto generador deja un conjunto 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]
• Si se denota la representación regular a la izquierda con forma matricial , la matriz de adyacencia de es . ${\displaystyle \rho _{\text{reg}}(g)(x)=gx}$ ${\displaystyle |G|\times |G|}$ ${\displaystyle [\rho _{\text{reg}}(g)]}$ ${\displaystyle \Gamma (G,S)}$ ${\textstyle A=\sum _{s\in S}[\rho _{\text{reg}}(s)]}$
• Cada carácter de grupo del grupo induce un vector propio de la matriz de adyacencia de . El valor propio asociado es ${\displaystyle \chi }$ ${\displaystyle G}$ ${\displaystyle \Gamma (G,S)}$
  $${\displaystyle \lambda _{\chi }=\sum _{s\in S}\chi (s),}$$
  que, cuando es abeliano, toma la forma ${\displaystyle G}$
  $${\displaystyle \sum _{s\in S}e^{2\pi ijs/|G|}}$$
  para números enteros 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. La base ortonormal correspondiente de los vectores propios viene dada por Es interesante observar que esta base propia es independiente del conjunto generador . ${\displaystyle j=0,1,\dots ,|G|-1.}$ ${\displaystyle \Gamma (G,S)}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle |G|}$ ${\displaystyle v_{j}={\tfrac {1}{\sqrt {|G|}}}{\begin{pmatrix}1&e^{2\pi ij/|G|}&e^{2\cdot 2\pi ij/|G|}&e^{3\cdot 2\pi ij/|G|}&\cdots &e^{(|G|-1)2\pi ij/|G|}\end{pmatrix}}.}$ ${\displaystyle S}$
  De manera más general, para conjuntos generadores simétricos, tome un conjunto completo de representaciones irreducibles de y dejémoslo con el conjunto de valores propios . Entonces el conjunto de valores propios de es exactamente donde el valor propio aparece con multiplicidad para cada aparición de como valor propio de ${\displaystyle \rho _{1},\dots ,\rho _{k}}$ ${\displaystyle G,}$ ${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$ ${\displaystyle \Lambda _{i}(S)}$ ${\displaystyle \Gamma (G,S)}$ ${\textstyle \bigcup _{i}\Lambda _{i}(S),}$ ${\displaystyle \lambda }$ ${\displaystyle \dim(\rho _{i})}$ ${\displaystyle \lambda }$ ${\displaystyle \rho _{i}(S).}$

Gráfico de clases de Schreier

Si, en cambio, se toman los vértices como clases laterales correctas 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 . Por el contrario, para los conjuntos generadores simétricos, la teoría espectral y de representación de están directamente vinculadas: tome un conjunto completo de representaciones irreducibles de y dejémoslo con valores propios . Entonces el conjunto de valores propios de es exactamente donde el valor propio aparece con multiplicidad para cada aparición de como valor propio de ${\displaystyle \Gamma (G,S)}$ ${\displaystyle \rho _{1},\dots ,\rho _{k}}$ ${\displaystyle G,}$ ${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$ ${\displaystyle \Lambda _{i}(S)}$ ${\displaystyle \Gamma (G,S)}$ ${\textstyle \bigcup _{i}\Lambda _{i}(S),}$ ${\displaystyle \lambda }$ ${\displaystyle \dim(\rho _{i})}$ ${\displaystyle \lambda }$ ${\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. ^[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 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 , el gráfico de Cayley es regular, se pueden utilizar técnicas espectrales para analizar las propiedades de expansión del gráfico. En particular, para los grupos abelianos, los valores propios del gráfico de Cayley son más fácilmente computables y están dados por un valor propio superior igual a , por lo que podemos usar la desigualdad de Cheeger para limitar la relación de expansión de los bordes usando la brecha espectral. ${\displaystyle S=S^{-1}}$ ${\displaystyle \Gamma (G,S)}$ ${\displaystyle |S|}$ ${\textstyle \lambda _{\chi }=\sum _{s\in S}\chi (s)}$ ${\displaystyle |S|}$

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

Si un grupo discreto tiene la propiedad de Kazhdan (T), y es un conjunto generador finito y simétrico de , entonces existe una constante que depende sólo de tal que para cualquier cociente finito del gráfico de Cayley de con respecto a la imagen de es un -expansor . ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle c>0}$ ${\displaystyle G,S}$ ${\displaystyle Q}$ ${\displaystyle G}$ ${\displaystyle Q}$ ${\displaystyle S}$ ${\displaystyle c}$

Por ejemplo, el grupo tiene la propiedad (T) y es generado por matrices elementales y esto proporciona ejemplos relativamente explícitos de gráficos en expansión. ${\displaystyle G=\mathrm {SL} _{3}(\mathbb {Z} )}$

Clasificación integral

Un gráfico integral es aquel cuyos valores propios son todos números enteros. Si bien la clasificación completa de las gráficas integrales sigue siendo un problema abierto, las gráficas de Cayley de ciertos grupos siempre son integrales. Utilizando caracterizaciones previas del espectro de gráficos de Cayley, tenga en cuenta que es integral si los valores propios de son integrales para cada representación de . ${\displaystyle \Gamma (G,S)}$ ${\displaystyle \rho (S)}$ ${\displaystyle \rho }$ ${\displaystyle G}$

Grupo simple integral de Cayley

Un grupo es integral simple de Cayley (CIS) si el gráfico de Cayley conectado es integral exactamente cuando el grupo electrógeno simétrico es el complemento de un subgrupo de . Un resultado de Ahmady, Bell y Mohar muestra que todos los grupos CIS son isomorfos a o para primos . ^[8] Es importante que realmente genere todo el grupo para que el gráfico de Cayley esté conectado. (Si no genera , el gráfico de Cayley aún puede ser integral, pero el complemento de no es necesariamente un subgrupo). ${\displaystyle G}$ ${\displaystyle \Gamma (G,S)}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} ,\mathbb {Z} /p^{2}\mathbb {Z} }$ ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{2}}$ ${\displaystyle p}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle S}$

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

• ${\displaystyle S=\{1,4\}}$: es un ciclo con valores propios ${\displaystyle \Gamma (G,S)}$ ${\displaystyle 5}$ ${\displaystyle 2,{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}}}$
• ${\displaystyle S=\{1,2,3,4\}}$: es con valores propios ${\displaystyle \Gamma (G,S)}$ ${\displaystyle K_{5}}$ ${\displaystyle 4,-1,-1,-1,-1}$

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

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. ^[8]

grupo integral cayley

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

La lista completa de grupos integrales de Cayley viene dada por , y el grupo dicíclico de orden , donde y es el grupo cuaternión. ^[8] La prueba se basa en dos propiedades importantes de los grupos integrales de Cayley: ${\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},S_{3}}$ ${\displaystyle 12}$ ${\displaystyle m,n\in \mathbb {Z} _{\geq 0}}$ ${\displaystyle Q_{8}}$

• Los subgrupos y las imágenes homomórficas de los grupos integrales de Cayley también son grupos integrales de Cayley.
• Un grupo es integral de Cayley si cada gráfico de Cayley conectado del grupo también es integral.

Grupos electrógenos normales y eulerianos

Dado un grupo general , un subconjunto es normal si está cerrado bajo conjugación por elementos de (generalizando la noción de subgrupo normal), y es euleriano si para cada , el conjunto de elementos que generan el grupo cíclico también está contenido en . Un resultado de 2019 de Guo, Lytkina, Mazurov y Revin demuestra que el gráfico de Cayley es integral para cualquier subconjunto normal euleriano , utilizando técnicas puramente teóricas de representación. ^[9] ${\displaystyle G}$ ${\displaystyle S\subseteq G}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle s\in S}$ ${\displaystyle \langle s\rangle }$ ${\displaystyle S}$ ${\displaystyle \Gamma (G,S)}$ ${\displaystyle S\subseteq G}$

La prueba de este resultado es relativamente breve: dado un subconjunto normal euleriano, seleccione no conjugado por pares para que sea la unión de las clases de conjugación . Luego, utilizando la caracterización del espectro de un gráfico de Cayley, se puede mostrar que los valores propios de están dados por caracteres irreducibles adoptados de . Cada valor propio en este conjunto debe ser un elemento de para una raíz primitiva de unidad (donde debe ser divisible por los órdenes de cada uno ). Debido a que los valores propios son enteros algebraicos, para demostrar que son integrales basta demostrar que son racionales, y basta demostrar que está fijado bajo cualquier automorfismo de . Debe haber algo relativamente primo para tal que para todos , y porque es a la vez euleriano y normal, para algunos . Envío de clases de conjugación de bijects, por lo que y tienen el mismo tamaño y simplemente permutan términos en la suma para . Por lo tanto, es fijo para todos los automorfismos de , por lo que es racional y, por tanto, integral. ${\displaystyle S}$ ${\displaystyle x_{1},\dots ,x_{t}\in G}$ ${\displaystyle S}$ ${\displaystyle \operatorname {Cl} (x_{i})}$ ${\displaystyle \Gamma (G,S)}$ ${\textstyle \left\{\lambda _{\chi }=\sum _{i=1}^{t}{\frac {\chi (x_{i})\left|\operatorname {Cl} (x_{i})\right|}{\chi (1)}}\right\}}$ ${\displaystyle \chi }$ ${\displaystyle G}$ ${\displaystyle \lambda _{\chi }}$ ${\displaystyle \mathbb {Q} (\zeta )}$ ${\displaystyle \zeta }$ ${\displaystyle m^{th}}$ ${\displaystyle m}$ ${\displaystyle x_{i}}$ ${\displaystyle \lambda _{\chi }}$ ${\displaystyle \sigma }$ ${\displaystyle \mathbb {Q} (\zeta )}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle \sigma (\chi (x_{i}))=\chi (x_{i}^{k})}$ ${\displaystyle i}$ ${\displaystyle S}$ ${\displaystyle \sigma (\chi (x_{i}))=\chi (x_{j})}$ ${\displaystyle j}$ ${\displaystyle x\mapsto x^{k}}$ ${\displaystyle \operatorname {Cl} (x_{i})}$ ${\displaystyle \operatorname {Cl} (x_{j})}$ ${\displaystyle \sigma }$ ${\displaystyle \lambda _{\chi }}$ ${\displaystyle \lambda _{\chi }}$ ${\displaystyle \mathbb {Q} (\zeta )}$ ${\displaystyle \lambda _{\chi }}$

En consecuencia, si es el grupo alterno y es un conjunto de permutaciones dado por , entonces la gráfica de Cayley es integral. (Esto resolvió un problema previamente abierto del Cuaderno de Kourovka). Además, cuando es el grupo simétrico y es el conjunto de todas las transposiciones o el conjunto de transposiciones que involucran un elemento particular, el gráfico de Cayley también es integral. ${\displaystyle G=A_{n}}$ ${\displaystyle S}$ ${\displaystyle \{(12i)^{\pm 1}\}}$ ${\displaystyle \Gamma (A_{n},S)}$ ${\displaystyle G=S_{n}}$ ${\displaystyle S}$ ${\displaystyle \Gamma (G,S)}$

Historia

Los gráficos de Cayley fueron considerados 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 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. ^[10]

Ver también

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

1. Prueba: Sea un automorfismo arbitrario del gráfico dirigido coloreado y sea la imagen de la identidad. Demostramos que para todos , por inducción en la distancia del borde de desde . Asumir . El automorfismo lleva cualquier borde de color a otro borde de color . Por tanto , y la inducción continúa. Como está conectado, esto se muestra para todos . ${\displaystyle \sigma :V(\Gamma )\to V(\Gamma )}$ ${\displaystyle \Gamma }$ ${\displaystyle h=\sigma (e)}$ ${\displaystyle \sigma (g)=hg}$ ${\displaystyle g\in V(\Gamma )}$ ${\displaystyle g}$ ${\displaystyle e}$ ${\displaystyle \sigma (g)=hg}$ ${\displaystyle \sigma }$ ${\displaystyle c_{s}}$ ${\displaystyle g\to gs}$ ${\displaystyle c_{s}}$ ${\displaystyle \sigma (g)\to \sigma (gs)}$ ${\displaystyle \sigma (gs)=\sigma (g)s=hgs}$ ${\displaystyle \Gamma }$ ${\displaystyle \sigma (g)=hg}$ ${\displaystyle g\in V(\Gamma )}$
2. Es fácil de modificar en un gráfico simple (sin color, no dirigido) cuyo grupo de simetría es isomorfo para : reemplazar los bordes dirigidos coloreados con árboles apropiados correspondientes a los colores. ${\displaystyle \Gamma }$ ${\displaystyle G}$ ${\displaystyle \Gamma }$

Notas

1. Magnus, Guillermo ; Karrass, Abraham; Solitario, 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.
2. Cayley, Arthur (1878). "Desideratas y sugerencias: N° 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 artículos matemáticos recopilados 10: 403–405.
3. Theron, Daniel Peter (1988), Una extensión del concepto de representaciones gráficamente regulares , Ph.D. tesis, Universidad de Wisconsin, Madison, pág. 46, señor  2636729.
4. Sabidussi, Gert (octubre de 1958). "Sobre una clase de gráficos sin puntos fijos". Actas de la Sociedad Matemática Estadounidense . 9 (5): 800–4. doi : 10.1090/s0002-9939-1958-0097068-7 . JSTOR  2033090.
5. Véase el teorema 3.7 de Babai, László (1995). «27. Grupos de automorfismo, isomorfismo, reconstrucción» (PDF) . En Graham, Ronald L .; Grötschel, Martín ; Lovász, László (eds.). Manual de combinatoria. vol. 1. Elsevier. págs. 1447-1540. ISBN 9780444823465.
6. Blanco, Arthur T. (1972). "Sobre el género de un grupo". Transacciones de la Sociedad Matemática Estadounidense . 173 : 203–214. doi : 10.1090/S0002-9947-1972-0317980-2 . SEÑOR  0317980.
7. Proposición 1.12 en Lubotzky, Alexander (2012). "Gráficos de expansión en matemática pura y aplicada". Boletín de la Sociedad Matemática Estadounidense . 49 : 113-162. arXiv : 1105.2389 . doi : 10.1090/S0273-0979-2011-01359-3 .
8. Ahmady, Azhvan; Campana, Jason; Mohar, Bojan (2014). "Gráficos y grupos integrales de Cayley". Revista SIAM de Matemática Discreta . 28 (2): 685–701. arXiv : 1307.6155 . doi :10.1137/130925487. S2CID  207067134.
9. Guo, W.; Lytkina, DV; Mazurov, VD; Revin, DO (2019). "Gráficos integrales de Cayley" (PDF) . Álgebra y Lógica . 58 (4): 297–305. arXiv : 1808.01391 . doi :10.1007/s10469-019-09550-2. S2CID  209936465.
10. Dehn, Max (2012) [1987]. Artículos sobre teoría de grupos y topología . Springer-Verlag. ISBN 978-1461291077.Traducido del alemán y con introducciones y apéndice de John Stillwell , y con apéndice de Otto Schreier .

enlaces externos

• diagramas de cayley
• Weisstein, Eric W. "Gráfico de Cayley". MundoMatemático .