Gráfico de Cayley

Gráfica definida 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 grafo de Cayley , también conocido como grafo de color de Cayley , diagrama de Cayley , diagrama de grupo o grupo de color , ^[1] es un grafo que codifica la estructura abstracta de un grupo . Su definición está sugerida por el teorema de Cayley (nombrado así por 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 grafos de Cayley los convierte en candidatos particularmente buenos para construir grafos expansores .

Definición

Sea un grupo y un conjunto generador de . El grafo de Cayley es un grafo dirigido con aristas coloreadas 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 de se le asigna un color . ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle c_{s}}$
• Para cada y , existe un borde dirigido de color desde el vértice correspondiente a al correspondiente a . ${\displaystyle g\in G}$ ${\displaystyle s\in S}$ ${\displaystyle c_{s}}$ ${\displaystyle g}$ ${\displaystyle gs}$

No todas las convenciones exigen que se genere el grupo. Si no es un conjunto generador de , 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 propio inverso, entonces normalmente se representa mediante un borde no dirigido. ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle s=s^{-1},}$

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

A veces se supone que el conjunto es simétrico ( ) y no contiene el elemento 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 grafo de Cayley es el ciclo . De manera más general, los grafos de Cayley de los grupos cíclicos finitos son exactamente los grafos 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 conjuntos generadores como conjunto generador) es el producto cartesiano de los gráficos de Cayley correspondientes. ^[3] Por lo tanto, 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áfica de Cayley del grupo diedro sobre dos generadores a y b ${\displaystyle D_{4}}$

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

• A la izquierda se muestra un gráfico de Cayley del grupo diedro en dos generadores y . 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 lo tanto, el gráfico es mixto: tiene ocho vértices, ocho flechas y cuatro aristas. La tabla de Cayley del grupo se puede derivar de la presentación del grupo A la derecha se muestra un gráfico de Cayley diferente de . sigue siendo la reflexión horizontal y está representada por líneas azules, y es una reflexión diagonal y está representada por líneas rosas. 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 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 .}$$ ${\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 representa 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 Dado que el grupo libre no tiene relaciones , el gráfico de Cayley no tiene ciclos : es el árbol infinito regular 4- . 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.}$
• En términos más generales, la red de Bethe o árbol de Cayley es el grafo de Cayley del grupo libre de generadores. Una presentación de un grupo por generadores corresponde a un homomorfismo sobreyectivo del grupo libre de generadores al grupo que define una función del árbol de Cayley al grafo de Cayley de . Interpretando topológicamente los grafos como complejos simpliciales unidimensionales , el árbol infinito simplemente conexo es la cubierta universal del grafo de Cayley; y el núcleo de la función es el grupo fundamental del grafo de Cayley. ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle G,}$ ${\displaystyle G}$

Parte de un gráfico de Cayley del grupo de Heisenberg. (Los colores son sólo para ayuda visual).

• A la derecha se muestra un gráfico de Cayley del grupo discreto de Heisenberg . 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 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 de cuatro dimensiones . ^[4] $${\displaystyle \left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}}$$ ${\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 por multiplicación izquierda (véase el teorema de Cayley ). Esto puede verse como la acción de sobre su grafo de Cayley. Explícitamente, un elemento asigna un vértice al vértice El conjunto de aristas del grafo de Cayley y su color se conserva por esta acción: la arista se asigna a la arista , ambas con 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, los grafos de Cayley son transitivos por vértice . Lo siguiente es una especie de recíproco:

Teorema de Sabidussi  :  Un grafo dirigido (sin etiquetar ni colorear) es un grafo de Cayley de un grupo si y solo si admite una acción simplemente transitiva de automorfismos de grafo ( es decir, preservando el conjunto de aristas dirigidas). ^[5] ${\displaystyle \Gamma }$ ${\displaystyle G}$ ${\displaystyle G}$

Para recuperar el grupo y el conjunto generador del grafo dirigido sin etiquetar , seleccione un vértice y etiquételo con el elemento identidad del grupo. Luego, etiquete cada vértice de con el elemento único de que se asigna a El conjunto de generadores de que da como resultado que el grafo de Cayley es el conjunto de etiquetas de los vecinos externos de . Dado que no está coloreado, podría tener más automorfismos de grafo dirigido que los mapas de multiplicación de la izquierda, por ejemplo, automorfismos de grupo de los cuales permutan . ${\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 grafo 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 grafo de Cayley tiene aristas dirigidas entrantes y salientes. En el caso de un conjunto generador simétrico con elementos, el grafo de Cayley es un grafo regular dirigido 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 recorridos 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 recorridos 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 dada es equivalente a resolver el Problema verbal para . ^[1] ${\displaystyle S.}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$
• Si es un homomorfismo de grupo sobreyectivo y las imágenes de los elementos del conjunto generador para son distintas, entonces induce un cubrimiento de grafos donde En particular, si un grupo tiene generadores, todos de orden diferente de 2, y el conjunto consiste en estos generadores junto con sus inversos, entonces el grafo de Cayley está cubierto por el árbol regular infinito de grado correspondiente al grupo libre en el mismo conjunto de generadores. ${\displaystyle f:G'\to G}$ ${\displaystyle S'}$ ${\displaystyle G'}$ $${\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),}$$ ${\displaystyle S=f(S').}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle \Gamma (G,S)}$ ${\displaystyle 2k}$
• Para cualquier grafo de Cayley finito, considerado como no dirigido, la conectividad de los vértices es al menos igual a 2/3 del grado del grafo. 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 es generador), la conectividad de los vértices es igual al grado. La conectividad de las aristas es en todos los casos igual al grado. ^[6]
• Si es la representación regular por la izquierda con forma matricial denotada , 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 del grupo induce un vector propio de la matriz de adyacencia de . El valor propio asociado es que, cuando es abeliano, toma la forma 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 está dada por Es interesante notar que esta base propia es independiente del conjunto generador . ${\displaystyle \chi }$ ${\displaystyle G}$ ${\displaystyle \Gamma (G,S)}$ $${\displaystyle \lambda _{\chi }=\sum _{s\in S}\chi (s),}$$ ${\displaystyle G}$ $${\displaystyle \sum _{s\in S}e^{2\pi ijs/|G|}}$$ ${\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 los conjuntos generadores simétricos, tomemos un conjunto completo de representaciones irreducibles de y sea con un conjunto de valores propios . Entonces, el conjunto de valores propios de es exactamente donde el valor propio aparece con multiplicidad para cada ocurrencia de como un 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áfica de coset de Schreier

Si, en cambio, se toman los vértices como clases laterales derechas de un subgrupo fijo, se obtiene una construcción relacionada, el grafo de clases laterales de Schreier , que es la base de la enumeración de clases laterales o del 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 grafo 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: tomemos un conjunto completo de representaciones irreducibles de y sea con valores propios . Entonces, el conjunto de valores propios de es exactamente donde el valor propio aparece con multiplicidad para cada ocurrencia de como un 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. ^[7]

Teoría de grupos geométricos

Para grupos infinitos, la geometría burda del grafo 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 tanto, una propiedad intrínseca del grupo. Esto solo es interesante para grupos infinitos: cada grupo finito es burdamente equivalente a un punto (o al grupo trivial), ya que uno puede elegir como conjunto finito de generadores todo el grupo.

Formalmente, para una elección dada 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 gruesa de este espacio es un invariante del grupo.

Propiedades de expansión

Cuando , el grafo de Cayley es -regular, por lo que se pueden utilizar técnicas espectrales para analizar las propiedades de expansión del grafo. En particular, para los grupos abelianos, los valores propios del grafo de Cayley son más fáciles de calcular y están dados por con el valor propio superior igual a , por lo que podemos utilizar la desigualdad de Cheeger para limitar la relación de expansión de las aristas utilizando 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 estos grafos de Cayley en expansión, en la forma de la propiedad de Kazhdan (T) . La siguiente afirmación es válida: ^[8]

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 grafo 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 está generado por matrices elementales y esto da ejemplos relativamente explícitos de gráficos expansores. ${\displaystyle G=\mathrm {SL} _{3}(\mathbb {Z} )}$

Clasificación integral

Un grafo integral es aquel cuyos valores propios son todos números enteros. Si bien la clasificación completa de los grafos integrales sigue siendo un problema abierto, los grafos de Cayley de ciertos grupos siempre son integrales. Utilizando caracterizaciones anteriores del espectro de grafos de Cayley, observe que es integral si y solo 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 grafo de Cayley conexo es integral exactamente cuando el conjunto generador 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 . ^[9] Es importante que realmente genere todo el grupo para que el grafo de Cayley sea conexo. (Si no genera , el grafo de Cayley puede seguir siendo 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 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 grafo integral es el complemento del grupo trivial. Por lo tanto, debe ser un grupo CIS. ${\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. ^[9]

Grupo integral de Cayley

Una noción ligeramente diferente es la de un grupo integral de Cayley , en el que cada subconjunto simétrico produce un grafo integral . Nótese que ya no tiene que generar todo el grupo. ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle \Gamma (G,S)}$ ${\displaystyle S}$

La lista completa de grupos integrales de Cayley está dada por , y el grupo dicíclico de orden , donde y es el grupo de cuaterniones. ^[9] 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 sólo si cada gráfico de Cayley conexo del grupo también es integral.

Conjuntos generadores 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 genera el grupo cíclico también está contenido en . Un resultado de 2019 de Guo, Lytkina, Mazurov y Revin demuestra que el grafo de Cayley es integral para cualquier subconjunto normal euleriano , utilizando técnicas puramente teóricas de representación. ^[10] ${\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 corta: dado un subconjunto normal euleriano, seleccione no conjugados por pares de modo que sea la unión de las clases de conjugación . Luego, utilizando la caracterización del espectro de un grafo de Cayley, se puede mostrar que los valores propios de están dados por caracteres irreducibles tomados de . Cada valor propio en este conjunto debe ser un elemento de para una raíz primitiva de la unidad (donde debe ser divisible por los órdenes de cada ). Debido a que los valores propios son números enteros algebraicos, para mostrar que son integrales basta con mostrar que son racionales, y basta con mostrar que es fijo bajo cualquier automorfismo de . Debe haber algún primo relativo a tal que para todo , y debido a que es tanto euleriano como normal, para algún . Enviar biyectos clases de conjugación, por lo que y tienen el mismo tamaño y simplemente permuta términos en la suma para . Por lo tanto es fijo para todos los automorfismos de , por lo que es racional y, por lo 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 alternado y es un conjunto de permutaciones dado por , entonces el grafo de Cayley es integral. (Esto resolvió un problema abierto previamente 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 grafo 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 grafos 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 grafos de Cayley bajo el nombre de Gruppenbild (diagrama de grupo), lo que condujo a la teoría geométrica de grupos actual. Su aplicación más importante fue la solución del problema verbal para el grupo fundamental de superficies con género ≥ 2, que es equivalente al problema topológico de decidir qué curvas cerradas en la superficie se contraen en un punto. ^[11]

Véase también

• Gráfico transitivo de vértice
• Conjunto generador de un grupo
• Conjetura de Lovász
• Ciclos cúbicos conexos
• Teoría de grafos algebraicos
• Gráfica de ciclos (álgebra)

1. Demostración: Sea un automorfismo arbitrario del grafo dirigido coloreado , y sea la imagen de la identidad. Demostramos que para todo , por inducción sobre la distancia de arista de desde . Supongamos que . El automorfismo lleva cualquier arista de color a otra arista de color . Por lo tanto , y la inducción procede. Como es conexo, esto demuestra para todo . ${\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 modificarlo en un gráfico simple (sin color, sin dirección) cuyo grupo de simetría es isomorfo a : reemplace los bordes dirigidos coloreados de con árboles apropiados correspondientes a los colores. ${\displaystyle \Gamma }$ ${\displaystyle G}$ ${\displaystyle \Gamma }$

Notas

1. Magnus, Wilhelm ; Karrass, Abraham; Solitar, Donald (2004) [1966]. Teoría de grupos combinatorios: presentaciones de grupos en términos de generadores y relaciones. Courier. ISBN 978-0-486-43830-6.
2. Cayley, Arthur (1878). "Desiderata y sugerencias: No. 2. La teoría de grupos: representación gráfica". American Journal of Mathematics . 1 (2): 174–6. doi :10.2307/2369306. JSTOR  2369306.En sus Collected Mathematical Papers 10: 403–405.
3. Theron, Daniel Peter (1988). Una extensión del concepto de representaciones gráficamente regulares (tesis doctoral). Universidad de Wisconsin, Madison. pág. 46. MR  2636729..
4. Bartholdi, Laurent (2017). "Crecimiento de grupos y productos de corona". En Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (eds.). Grupos, gráficos y paseos aleatorios: artículos seleccionados del taller celebrado en Cortona, del 2 al 6 de junio de 2014. London Math. Soc. Lecture Note Ser. Vol. 436. Cambridge Univ. Press, Cambridge. págs. 1–76. arXiv : 1512.07044 . ISBN 978-1-316-60440-3.Señor 3644003  .
5. Sabidussi, Gert (octubre de 1958). "Sobre una clase de grafos libres de punto fijo". Actas de la American Mathematical Society . 9 (5): 800–4. doi : 10.1090/s0002-9939-1958-0097068-7 . JSTOR  2033090.
6. 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.
7. White, Arthur T. (1972). "Sobre el género de un grupo". Transactions of the American Mathematical Society . 173 : 203–214. doi : 10.1090/S0002-9947-1972-0317980-2 . MR  0317980.
8. Proposición 1.12 en Lubotzky, Alexander (2012). "Gráficos expansores en matemáticas puras y aplicadas". Boletín de la Sociedad Americana de Matemáticas . 49 : 113–162. arXiv : 1105.2389 . doi : 10.1090/S0273-0979-2011-01359-3 .
9. Ahmady, Azhvan; Bell, Jason; Mohar, Bojan (2014). "Gráficos y grupos integrales de Cayley". Revista SIAM de Matemáticas Discretas . 28 (2): 685–701. arXiv : 1307.6155 . doi :10.1137/130925487. S2CID  207067134.
10. 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.
11. 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 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 .