Automorfismi di grafi

[Catraga]

Un problema ormai classico in combinatoria...
Trovare il gruppo di automorfismi del grafo di Petersen.

[Nonno Bassotto]

Potrebbe essere utile definire prima cos'è il grafo di Petersen, per chi non lo sa (io)

[talpuz]

http://en.wikipedia.org/wiki/Petersen_graph

(nemmeno io lo sapevo, chiaro )

[Nonno Bassotto]

Sì, sapevo che potevo cercare su Wikipedia. Ho scritto più che altro per incoraggiare Catraga a rendere un po' meno oscuro il problema. Altrimenti c'era il rischio che l'insieme delle persone che sanno cos'è il grafo di Petersen coincidesse con l'insieme delle persone che sanno qual'è il gruppo degli automorfismi del grafo di Petersen (e magari il tutto coincideva con {Catraga}).
Ciao

[Nonno Bassotto]

Comunque in breve il grafo di Petersen
-ha come vertici le coppie (a,b) con a,b appartenenti a {1,2,...,5}
-due vertici sono connessi se, e solo se, le coppie sono disgiunte

[ma_go]

uhm.. scusa, le coppie $ (a,b) $ o $ \{a \neq b\} $?
per inciso, a me torna la seconda (e mi torna anche con quello che ho letto essere il gruppo di automorfismi...)
(però avevo trovato [in modo elementarissimo] la cardinalità di questo insieme.. è un invito a tutti voi)

[OT]

[...] {1,2,...,5}.

ehm.. se scrivevi 3,4 occupavi lo stesso spazio :p
[/OT]

[Catraga]

lol...
Comunque, per rassicurarvi, il gruppo di autmorfismi non ha una costruzione "strana"...

[ma_go]

beh, siccome ho barato (ho letto su wikipedia qual è effettivamente questo gruppo), posto una soluzione in bianco...
e poi in bianco posto quello che avevo fatto per conto mio...

è evidente, dai post di Nonno Bassotto, e dalla sua "definizione equivalente" di grafo di petersen P, che il gruppo degli automorfismi Aut(P) è un sottogruppo di S5, quindi Aut(P)<S5. d'altro canto, ogni permutazione di S5 corrisponde ad un automorfismo di P, quindi Aut(P) = S5.

...mentre...

fissiamo un vertice di partenza v. questo può essere mandato in un qualunque vertice v'. i tre vertici w1, w2, w3 direttamente collegati a v dovranno essere mandati nei tre vertici collegati direttamente a v' (che chiamiamo w1', w2', w3'), e qualunque scelta delle funzioni da {w1, w2, w3} in {w1', w2', w3'} funziona. quindi abbiamo 60 scelte, sinora. ora, con un po' di "lavoro sporco", ci si accorge che basta fissare un altro l'immagine di un solo altro vertice per determinare completamente l'automorfismo, e quessto ci dà solamente due possibilità (per ovvi motivi).
quindi |Aut(P)| = 120.

[Catraga]

Altro modo, senza ricorrere alla costruzione equivalente:
Poiche'
$ P_5=\overline{L(K_5)} $
si ha:
$ Aut(P_5)\cong Aut(\overline{L(K_5)})\cong Aut(L(K_5))\cong Aut(K_5)\cong \mathbb{S}_5 $
Dove: $ L(G) $ indica il line graph, o duale per archi, di $ G $; inoltre si sono usati i risultati:
$ Aut(\overline{G})\cong Aut(G) $
e
$ Aut(L(G))\cong Aut(G) $