Grupos de automorfismos

Automorfismos de grafos

Definici ́on

Un isomorfismo de un grafo G a un grafo H es una biyecci ́on f del conjunto de v ́ertices de

G al de H, tal que uf ∼wf (en H) si y s ́olo si u ∼v (en G). En ese caso se dice que G y

H son isomorfos y se denota como G ∼= H.

Paola C. (Unidad Acad ́emica de Matem ́aticas, UAZ.) •Automorfismos de grafos. •17.09.2021 •(4/14)

Automorfismos de grafos

El grupo de automorfismos es un invariante algebraico de un grafo.

• El producto directo G1 ×G2 de dos grupos de permutaciones G1, G2 (actuando en los

conjuntos Ω1, Ω2) es el grupo de permutaci ́on en la uni ́on disjunta Ω1 ∪Ω2, cuyos

elementos son pares ordenados (g1, g2) para gi ∈Gi; la acci ́on est ́a dada por

v(g1, g2) =

{vg1 si v ∈Ω1,

vg2 si v ∈Ω2

• Si G2 es un grupo de permutaci ́on en {1, ..., n}, entonces el producto corona G1 oG2 es

generado por el producto directo de n copias de G1, junto con los elementos de G2 que

act ́uan en esas n copias de G1

Paola C. (Unidad Acad ́emica de Matem ́aticas, UAZ.) •Automorfismos de grafos. •17.09.2021 •(5/14)

Automorfismos de grafos

Teorema

1. Un grafo y su complemento tienen el mismo grupo de automorfismo.

2. Suponiendo que las componentes conexas de G consisten en n1 copias de G1, ..., nr

copias de Gr, donde G1, ..., Gr son no isomorfos a pares. Entonces

Aut(G) = (Aut(G1) oSn1) ×... ×(Aut(Gr) oSnr).

3. Aut(Kn) = Sn

Paola C. (Unidad Acad ́emica de Matem ́aticas, UAZ.) •Automorfismos de grafos. •17.09.2021 •(6/14)

Automorfismos de grafos t ́ıpicos

Automorfismos de grafos t ́ıpicos.

Teorema

Casi todos los grafos no tienen automorfismos no triviales.

Esto quiere decir que la proporci ́on de grafos con n v ́ertices que tienen un automorfismo no

trivial tiende a cero cuando n →∞. Y lo cual implica que casi todos los grafos pueden ser

etiquetados de n! distintas formas.

Adem ́as existen m ́etodos para el etiquetado can ́onico de un grafo y para casi todos el

etiquetado can ́onico es ́unico y se puede encontrar en tiempo polinomial.

Paola C. (Unidad Acad ́emica de Matem ́aticas, UAZ.) •Automorfismos de grafos. •17.09.2021 •(7/14)

Automorfismos de grafos t ́ıpicos.

El teorema sigue siendo v ́alido para varias clases especiales de gr ́aficos, incluidos los

gr ́aficos regulares de valencia fija k > 2 (incluso podemos permitir que la valencia crezca,

no demasiado r ́apido, respecto a n), o los grafos fuertemente regulares de cuadrado latino.

Paola C. (Unidad Acad ́emica de Matem ́aticas, UAZ.) •Automorfismos de grafos. •17.09.2021 •(8/14)

Grupos de permutaci ́on

Grupos de permutaci ́on

...