Grafo de Cayley

Em matemática, área da teoria dos grafos, um grafo de Cayley, também conhecido como grafo colorido de Cayley, diagrama de Cayley, diagrama de grupo, ou grupo colorido é um grafo que codifica a estrutura abstrata de um grupo. Sua definição é sugerida pelo teorema de Cayley (nomeado em honra a Arthur Cayley) e usa um conjunto de geradores específico, usualmente finito, para o grupo. É um instrumento central em combinatória e teoria geométrica de grupos.

O grafo de Cayley do grupo livre em dois geradores a e b

Famílias de grafos definidos por seus automorfismos
distância-transitivo	$\rightarrow$	distância-regular	$\leftarrow$	fortemente regular
$\downarrow$
simétrico (arco-transitivo)	$\leftarrow$	t-transitivo, t ≥ 2		.
$\downarrow$ (se conectado)
transitivo nos vértices e nas arestas	$\rightarrow$	aresta-transitivo e regular	$\rightarrow$	aresta-transitivo
$\downarrow$		$\downarrow$
vértice-transitivo	$\rightarrow$	regular
$\uparrow$
grafo de Cayley		antissimétrico		assimétrico

Definição

Suponha que $G$ seja um grupo e $S$ seja um conjunto de geradores. O grafo de Cayley $\Gamma =\Gamma (G,S)$ é um grafo direcionado colorido construído como se segue

• A cada elemento $g$ de $G$ é atribuído um vértice: o conjunto de vértices $V(\Gamma )$ de $\Gamma$ é identificado com $G.$
• A cada gerador $s$ de $S$ é atribuída uma cor $c_{s}.$
• Para qualquer $g\in G,s\in S,$ os vértices correspondentes aos elementos $g$ e $gs$ são unidos por uma aresta de cor $c_{s}.$ Assim, o conjunto de arestas $E(\Gamma )$ consiste em pares da forma $(g,gs),$ com $s\in S$ proporcionando a cor.

Na teoria geométrica de grupos, o conjunto $S$ é geralmente assumido ser finito, simétrico, isto é $S=S^{-1},$ e não contendo o elemento identidade do grupo. Neste caso, o grafo de Cayley incolor é um grafo comum: suas arestas não são orientadas e não contém laços se e somente se $1\notin S.$

Exemplos

• Suponha que $G=\mathbb {Z}$ é o grupo cíclico infinito e o conjunto S consiste em um gerador padrão e sua inversa (-1 na notação aditiva), então o grafo de Cayley é uma cadeia infinita.

• Similarmente, se $G=\mathbb {Z} _{n}$ é o grupo cíclico finito de ordem n e o conjunto S consiste de dois elementos, o gerador padrão de G e o seu inverso, então o grafo de Cayley é o ciclo $C_{n}.$

• O grafo de Cayley do produto direto de grupos é o produto cartesiano dos grafos de Cayley correspondentes. Assim, o grafo de Cayley do grupo abeliano $\mathbb {Z} ^{2}$ com o conjunto de geradores que consiste em quatro elementos $(\pm 1,0),(0,\pm 1)$ é a grade no plano $\mathbb {R} ^{2},$ enquanto que para o produto direto $\mathbb {Z} _{n}\times \mathbb {Z} _{m}$ com geradores semelhantes o grafo de Cayley é a grade finita $n\times m$ em um toro.

O grafo de Cayley do grupo diedro D₄ em dois geradores α e β

• O grafo Cayley do grupo diedro D₄ em dois geradores α e β é descrito à esquerda. As setas vermelhas representam a multiplicação à esquerda pelo elemento α. Uma vez que o elemento β é auto-inversível, as linhas azuis que representam a multiplicação à esquerda pelo elemento β são não direcionadas. Portanto, o grafo é misto: ele tem oito vértices, oito setas, e quatro arestas. A tabela Cayley do grupo D₄ pode ser derivada a partir da apresentação do grupo

$$\langle \alpha ,\beta |\alpha ^{4}=\beta ^{2}=e,\alpha \beta =\beta \alpha ^{3}\rangle .$$

Ver também

• Grafo vértice-transitivo
• Conjunto gerador de um grupo

Ligações externas

• Diagramas Cayley