Grafo di Cayley

In matematica, il grafo di Cayley è un grafo associato ad un gruppo, che traduce alcune proprietà algebriche del gruppo in proprietà metriche del grafo. Il grafo di Cayley è uno strumento centrale in topologia e nella teoria geometrica dei gruppi.

Sia ${\displaystyle G}$ un gruppo e ${\displaystyle S}$ un insieme di generatori per ${\displaystyle G}$. Il grafo di Cayley di ${\displaystyle G}$ è un grafo costruito a partire da ${\displaystyle G}$ e ${\displaystyle S}$ nel modo seguente.^[1]

• I vertici del grafo sono gli elementi di ${\displaystyle G}$,
• gli spigoli del grafo sono le coppie ${\displaystyle (g,gs)}$ al variare di ${\displaystyle g}$ in ${\displaystyle G}$ e ${\displaystyle s}$ in ${\displaystyle S}$.

Si può decidere di dare un colore diverso ad ogni generatore ${\displaystyle s\in S}$ ed assegnare quel colore allo spigolo ${\displaystyle (g,gs)}$. Si può anche dare un'orientazione allo spigolo, che parte da ${\displaystyle g}$ ed arriva in ${\displaystyle gs}$.

Sia ${\displaystyle G=\mathbb {Z} }$ il gruppo degli interi e ${\displaystyle S=\{1\}}$ consista del generatore standard 1. Il grafo di Cayley è l'insieme di vertici ${\displaystyle \mathbb {Z} }$, con un segmento per ogni coppia ${\displaystyle (n,n+1)}$. Topologicamente il grafo di Cayley è quindi una retta.

Sia ${\displaystyle G=\mathbb {Z} _{n}}$ il gruppo ciclico di ordine ${\displaystyle n}$ e ${\displaystyle S=\{1\}}$ il generatore standard. Il grafo di Cayley è l'insieme di vertici ${\displaystyle 0,1,\ldots ,n-1}$, con un segmento per ogni coppia ${\displaystyle (i,i+1)}$, inclusa la coppia ${\displaystyle (n-1,0)}$. Il grafo di Cayley è quindi un poligono con ${\displaystyle n}$ lati.

Il grafo di Cayley del prodotto di gruppi è il prodotto cartesiano dei grafi di Cayley di ogni fattore, purché l'insieme dei generatori per il prodotto sia scelto in modo naturale sulla base dei generatori dei singoli fattori^[2].

Il grafo di Caley di ${\displaystyle \mathbb {Z} ^{2}}$ con generatori ${\displaystyle (1,0)}$ e ${\displaystyle (0,1)}$ è una griglia nel piano ${\displaystyle \mathbb {R} ^{2}}$.

Il grafo di Cayley del gruppo diedrale ${\displaystyle D_{4}}$ presentato nel modo seguente

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

con generatori ${\displaystyle a}$ e ${\displaystyle b}$ è mostrato nella figura a sinistra. Nella figura di destra è mostrato il grafo di Cayley dello stesso gruppo ${\displaystyle D_{4}}$ rispetto ad un altro insieme di generatori.

Il grafo di Cayley del gruppo libero con due generatori ${\displaystyle a}$ e ${\displaystyle b}$ è mostrato più in alto: si tratta di un albero infinito in cui ogni vertice è adiacente a quattro spigoli.

• Generatori di un gruppo
• Gruppo libero

• Wikimedia Commons contiene immagini o altri file su grafo di Cayley

• (EN) Eric W. Weisstein, Grafo di Cayley, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica