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.

Definizione

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

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

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

Esempi

Gruppi abeliani

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

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

Prodotto diretto

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 $\mathbb {Z} ^{2}$ con generatori $(1,0)$ e $(0,1)$ è una griglia nel piano $\mathbb {R} ^{2}$ .

Gruppo diedrale

Grafo di Cayley del gruppo diedrale

D_{4}

con generatori

a

e

b

Grafo di Cayley di

D_{4}

con generatori

b

e

c

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

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

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

Gruppo libero

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

Note

^ Arthur Cayley, Desiderata and suggestions: No. 2. The Theory of groups: graphical representation, in Amer. J. Math., vol. 2, n. 1, 1878, pp. 174–176, JSTOR 2369306.
^ Nel prodotto di due gruppi $G_1\times G_2$ si prendono come generatori gli elementi $(s_1,0)$ e $(0,s_2)$ al variare di $s_1$ e $s_2$ fra i generatori di $G_1$ e $G_2$.

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file su grafo di Cayley

Collegamenti esterni

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

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

[1] Arthur Cayley, Desiderata and suggestions: No. 2. The Theory of groups: graphical representation, in Amer. J. Math., vol. 2, n. 1, 1878, pp. 174–176, JSTOR 2369306.

[2] Nel prodotto di due gruppi $G_1\times G_2$ si prendono come generatori gli elementi $(s_1,0)$ e $(0,s_2)$ al variare di $s_1$ e $s_2$ fra i generatori di $G_1$ e $G_2$.

[1]

[2]