Graf de Cayley

En matemàtiques, un graf de Cayley, també conegut com a diagrama de Cayley o diagrama de grup^[1] és un graf que codifica l'estructura abstracta d'un grup. La seva definició ve suggerida pel teorema de Cayley (que rep aquest nom pel matemàtic britànic Arthur Cayley) i fa servir un conjunt de generadors determinat, habitualment finit, per al grup. És una eina central en la teoria de grups combinatòria i geomètrica.

Suposem que ${\displaystyle G}$ és un grup i ${\displaystyle S}$ n'és un conjunt generador. El graf de Cayley ${\displaystyle \Gamma =\Gamma (G,S)}$ és un graf dirigit acolorit construït de la següent manera:^[2]

• A cada element ${\displaystyle g}$ de ${\displaystyle G}$ se li assigna un vèrtex: el conjunt de vèrtexs ${\displaystyle V(\Gamma )}$ de ${\displaystyle \Gamma }$ s'identifica amb ${\displaystyle G}$.
• A cada generador ${\displaystyle s}$ de ${\displaystyle S}$ se li assigna un color ${\displaystyle c_{s}}$.
• Per a qualssevol ${\displaystyle g\in G}$ i ${\displaystyle s\in S}$, els vèrtexs corresponents als elements ${\displaystyle g}$ i ${\displaystyle gs}$ estan connectats per una aresta dirigida de color ${\displaystyle c_{s}}$. Així, el conjunt d'arestes ${\displaystyle E(\Gamma )}$ consisteix en parells de la forma ${\displaystyle (g,gs),}$ on ${\displaystyle s\in S}$ hi proporciona el color.

En teoria geomètrica de grups, el conjunt ${\displaystyle S}$ s'acostuma a assumir que és finit, simètric (és a dir, ${\displaystyle S=S^{-1}}$) i que no conté l'element neutre del grup. En aquest cas, el graf de Cayley sense acolorir és un graf ordinari: les seves arestes no són dirigides, i no conté bucles (cicles d'un sol element).

• Suposem que ${\displaystyle G=\mathbb {Z} }$ és el grup cíclic infinit, i que el conjunt S consisteix del generador habitual 1 i el seu invers (−1 en notació additiva). Llavors el seu graf de Cayley és un camí infinit.
• De manera semblant, si ${\displaystyle G=\mathbb {Z} _{n}}$ és el grup cíclic finit d'ordre n, i el conjunt S consisteix en dos elements, el generador habitual de G i el seu invers, llavors el graf de Cayley és el cicle ${\displaystyle C_{n}}$. En general, els grafs de Cayley dels grups cíclics finits són exactament els grafs circulants.
• El graf de Cayley del producte directe de grups (amb el producte cartesià dels conjunts generadors com a conjunt generador) és el producte cartesià dels corresponents grafs de Cayley.^[3] Així, el graf de Cayley del grup abelià ${\displaystyle \mathbb {Z} ^{2}}$ amb el conjunt de generadors consistent dels quatre elements ${\displaystyle (\pm 1,0),(0,\pm 1)}$ és el reticle infinit sobre el pla ${\displaystyle \mathbb {R} ^{2}}$, mentre que pel producte directe ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{m}}$ amb els mateixos generadors, el graf de Cayley és el reticle finit ${\displaystyle n\times m}$ sobre un tor.

• A l'esquerra (figura 1) es mostra un graf de Cayley del grup diedral D₄ sobre dos generadors a i b. Les fletxes vermelles representen la multiplicació per l'esquerra per l'element a. Com que l'element b és invers d'ell mateix, les línies blaves que representen la multiplicació per l'esquerra per b són arestes no dirigides. Per tant, el graf és mixt: té 8 vèrtexs, 8 arestes dirigides i 4 arestes no dirigides. La taula de Cayley del grup D₄ es pot calcular a partir de la presentació de grup

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

A la dreta (figura 2) es mostra un graf de Cayley diferent per a D₄. L'element b continua essent la reflexió horitzontal, representada per línies blaves; l'element c és una reflexió diagonal, representada per línies verdes. Com que ambdues reflexions són inverses d'elles mateixes, el graf de Cayley de la dreta és totalment no dirigit. Aquest graf correspon a la presentació

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

• El graf de Cayley del grup lliure sobre dos generadors a, b corresponent al conjunt S = {a, b, a⁻¹, b⁻¹} es mostra a l'inici de l'article, i e representa l'element neutre. Si es recorre una aresta cap a la dreta, hom té la multiplicació per la dreta per a, mentre que si es recorre una aresta cap amunt, hom té la multiplicació per b. Com que el grup lliure no té relacions, el graf de Cayley no té cicles. Aquest graf de Cayley és un element principal en la demostració de la paradoxa de Banach-Tarski.

• A la dreta (figura 3) es mostra un graf de Cayley del grup de Heisenberg discret ${\displaystyle \left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}}$. Els generadors utilitzats a la figura són les tres matrius X, Y, Z donades per les tres permutacions de 1, 0, 0 per les entrades x, y, z. Aquestes matrius satisfan les relacions

${\displaystyle Z_{}^{}=XYX^{-1}Y^{-1},\ XZ=ZX,\ YZ=ZY}$. Aquest és un grup infinit no commutatiu, i encara que és un espai tridimensional, el graf de Cayley té una taxa de creixement en dimensió 4.

El grup ${\displaystyle G}$ actua sobre ell mateix per multiplicació per l'esquerra (vegeu el teorema de Cayley). Això es pot visualitzar com l'acció de ${\displaystyle G}$ sobre el seu graf de Cayley. Explícitament, un element ${\displaystyle h\in G}$ envia un vèrtex ${\displaystyle g\in V(\Gamma )}$ al vèrtex ${\displaystyle hg\in V(\Gamma )}$. El conjunt d'arestes contingudes al graf de Cayley queda conservat per aquesta acció: l'aresta ${\displaystyle (g,gs)}$ es transforma en l'aresta ${\displaystyle (hg,hgs)}$. La multiplicació per l'esquerra de qualsevol grup sobre ell mateix és simplement transitiva, en particular, el graf de Cayley és vèrtex-transitiu. Això porta a la següent caracterització dels grafs de Cayley:

Per recuperar el grup ${\displaystyle G}$ i el conjunt generador ${\displaystyle S}$ a partir del graf de Cayley ${\displaystyle \Gamma =\Gamma (G,S)}$, cal seleccionar un vèrtex ${\displaystyle v_{1}\in V(\Gamma )}$ i etiquetar-lo com l'element neutre del grup. Llavors s'etiqueta cada vèrtex ${\displaystyle v}$ de ${\displaystyle \Gamma }$ com l'únic element de ${\displaystyle G}$ que transforma ${\displaystyle v_{1}}$ en ${\displaystyle v.}$ El conjunt ${\displaystyle S}$ de generadors de ${\displaystyle G}$ que té com a resultat ${\displaystyle \Gamma }$ per graf de Cayley és el conjunt de vèrtexs adjacents al vèrtex seleccionat. El conjunt generador és finit (aquesta és una hipòtesi habitual per als grafs de Cayley) si i només si el graf és localment finit (és a dir, cada vèrtex és adjacent a un nombre finit d'arestes).

• Si un element ${\displaystyle s}$ del conjunt generador és el seu propi invers, ${\displaystyle s=s^{-1}}$, llavors s'acostuma a representar amb una aresta no dirigida.
• El graf de Cayley ${\displaystyle \Gamma (G,S)}$ depèn d'una manera essencial de l'elecció del conjunt ${\displaystyle S}$ de generadors. Per exaemple, si el conjunt generador ${\displaystyle S}$ té ${\displaystyle k}$ elements, llavors cada vèrtex del graf de Cayley té ${\displaystyle k}$ arestes dirigides d'entrada i ${\displaystyle k}$ arestes dirigides de sortida. En el cas d'un conjunt generador simètric ${\displaystyle S}$ amb ${\displaystyle r}$ elements, el graf de Cayley és un graf regular dirigit de grau ${\displaystyle r}$.
• Els cicles (o camins tancats) indiquen relacions entre els elements de ${\displaystyle S}$. InEn la construcció més elaborada del complex de Cayley d'un grup, els camins tancats corresponents a les relacions estan "farcits" per polígons. Això significa que el problema de construir el graf de Cayley d'una presentació donada ${\displaystyle {\mathcal {P}}}$ és equivalent a resoldre el problema de la paraula per a ${\displaystyle {\mathcal {P}}}$.^[1]
• Si ${\displaystyle f:G'\to G}$ és un homomorfisme de grups exhaustiu i les imatges dels elements del conjunt generador ${\displaystyle S'}$ per ${\displaystyle G'}$ són diferents, llavors indueix un revestiment de grafs

${\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),\quad }$ on ${\displaystyle S=f(S')}$.

En particular, si un grup ${\displaystyle G}$ té ${\displaystyle k}$ generadors, tots d'ordre diferent de 2, i el conjunt ${\displaystyle S}$ consisteix d'aquests generadors i els seus inversos, llavors el graf de Cayley ${\displaystyle \Gamma (G,S)}$ està revestit per l'arbre regular infinit de grau ${\displaystyle 2k}$ corresponent al grup lliure sobre el mateix conjunt de generadors.

• Es pot construir un graf ${\displaystyle \Gamma (G,S)}$ encara que el conjunt ${\displaystyle S}$ no generi el grup ${\displaystyle G}$. Tanmateix, no és connex i no es considera que sigui un graf de Cayley. En aquest cas, cada component connexa del graf representa una classe lateral del subgrup generat per ${\displaystyle S}$.
• Per a qualsevol graf de Cayley, vist com un graf no dirigit, la vèrtex-connectivitat és, com a mínim, igual a 2/3 del grau del graf. Si el conjunt generador és mínim (és a dir, si s'elimina un element qualsevol del conjunt generador i, si hi està contingut, el seu invers, el conjunt restant no és generador), llavors la vèrtex-connectivitat és igual al grau. L'aresta-connectivitat és sempre igual al grau.^[5]

Estudiant la matriu d'adjacència del graf, i en particular aplicant els teoremes de la teoria espectral de grafs, es pot obtenir informació sobre l'estructura del grup.

Per a grups infinits, la geometria grollera del graf de Cayley és de vital importància en la teoria geomètrica de grups. En el cas d'un grup finitament generat, això és independent de l'elecció del conjunt finit de generadors, i per tant és una propietat intrínseca del grup. Aquesta propietat és interessant només per a grups infinits: tot grup finit és equivalent, segons la geometria grollera, a un sol punt (o al grup trivial), ja que hom pot prendre com a conjunt finit de generadors la totalitat del grup.

Formalment, donada una elecció de generadors, hom té la mètrica de paraules (la distància natural sobre el graf de Cayley), la qual determina un espai mètric. La classe d'equivalència grollera d'aquest espai és un invariant del grup.

El graf de Cayley fou introduït inicialment, en el cas de grups finits, pel matemàtic britànic Arthur Cayley l'any 1878.^[2] Max Dehn, en les seves obres inèdites sobre teoria de grups dels anys 1909-10, va reintroduir els grafs de Cayley sota el terme Gruppenbild (diagrama de grup), la qual cosa va portar a la teoria geomètrica de grups de l'actualitat. La seva principal aplicació fou la solució al problema de la paraula de superfícies amb gènere ≥ 2, el qual és equivalent al problema topològic de decidir quines corbes tancades sobre la superfície es contrauen en un punt.^[6]

El reticle de Bethe, o arbre de Cayley, és el graf de Cayley del grup lliure sobre n generadors. Una presentació del grup G per n generadors correspon a una aplicació exhaustiva del grup lliure de n generadors en el grup G i, des del punt de vista dels grafs de Cayley, de l'arbre de Cayley en el graf de Cayley. Això també es pot interpretar (en topologia algebraica) com el revestiment universal del graf de Cayley, que en general no és simplement connex.

• Diagrames de Cayley
• Weisstein, Eric W., «Cayley graph» a MathWorld (en anglès).