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

Dado un grupo de permutaci ́on G en el conjunto Ω, podemos describir todos los grafos en

los que actua G de la siguiente forma. Existe una acci ́on de G en Ω ×Ω, dada por

(u, v)g = (ug, vg). Sea U el conjunto de todas las ́orbitas de G en Ω ×Ω que constan de

pares de elementos distintos. La ́orbita emparejada con O, la definimos de manera natural

como O∗= {(v, u) : (u, v) ∈O}. Sea S cualquier subconjunto de U , que contiene la ́orbita

emparejada para cada uno de sus elementos, y dfinimos un grafo G(S) en el conjunto de

v ́ertices Ω con la regla u ∼v en G(S) si y s ́olo si (u, v) ∈O para alg ́un O ∈S. Entonces

G(S) es un grafo simple que admite a G como un grupo de automorfismos; y cada grafo de

este tipo surge de esta construcci ́on.

Modificando un poco las condiciones para S, la construcci ́on anterior se puede adaptar

para grafos dirigidos, grafos con lazos y multigrafos.

...