Grafi con gruppi di automorfismi abeliani

[edriv]

Dimostrare che per ogni gruppo abeliano finito $ ~ G $ esiste un grafo R tale che il gruppo degli automorfismi di R è G.

Nota: il grafo non è orientato, un automorfismo di R è una permutazione dei suoi elementi tale che esiste l'arco (a,b) se e soltanto se esiste l'arco (f(a), f(b)).

E' un bel problema di creatività

[MindFlyer]

E' valido per tutti i gruppi finiti (anche non abeliani), e si chiama Teorema di Frucht.

[edriv]

Sì, io comunque ho detto abeliani perchè così il problema è fattibile e divertente, il teorema di Frucht non ho idea di come si faccia (anche se è certamente interessante).

[MindFlyer]

Col teorema fondamentale dei gruppi abeliani finiti sembra facile.
Forse non vuoi che si usi questo teorema?

[edriv]

Sìsì, bisogna appunto usare quello.
- trovare un grafo che abbia come automorfismi un gruppo ciclico
- costruire un grafo che abbia come automorfismi il prodotto diretto di due gruppi

[MindFlyer]

Ok beh, allora scompongo $ G $ come prodotto di $ G_i=\mathbb{Z}_{p_i^n_i} $. Poi ogni $ G_i $ diventa un grafo "ad anello" dello stesso ordine. Dopodiché, se vi sono anelli uguali, li differenzio attaccando ad ogni nodo una "fila" di altri nodi, in modo che nodi dello stesso anello abbiano file della stessa lunghezza, e che le lunghezze siano diverse per ogni anello.

[EvaristeG]

forse intendeva connesso?

[MindFlyer]

Cambia poco, si uniscono tutte le "file" ad un unico nodo (ovviamente non si ammettono più anelli senza file).

[edriv]

Sì perfetto... l'unica cosa poco chiara è cosa sia un grafo ad anello.

[MindFlyer]

$ \Big(\big\{x_1,\ldots , x_n \big\}, \big\{ (x_1,x_2), (x_2,x_3), \ldots, (x_{n-1},x_n), (x_n,x_1)\big\} \Big) $.
Più eventualmente le coppie simmetriche, a seconda di come rappresenti gli archi nei grafi non orientati. Oppure senza una delle due coppie nel caso n=2. Insomma, hai capito. Un anello, cazzo! Mica penserai alle strutture algebriche. La prima volta che l'ho scritto, ho usato le virgolette apposta perché i nerd non fraintendessero. Fai 2^ superiore, se dico anello devi pensare ad un tondo, non alle supercazzole!

EDIT:
Ok, MathWorld li chiama grafi ciclici. Impara, MindFlyer, impara.

[edriv]

Minde minde... se la soluzione fosse stata quella, forse ci sarei anche arrivato ad immaginare che un anello era una cosa con quella forma.

Peccato che tra gli automorfismi di quel grafo ci sono anche le simmetrie, non solo le rotazioni... ma noi volevamo un gruppo ciclico, no?

[MindFlyer]

Oh sì, hai ragione. Tra un po' ci penso.

[MindFlyer]

Ecco, ho corretto.
Sostanzialmente per togliere le simmetrie dotiamo un grafo ad anello di un "verso di percorrenza". Ovvero $ \mathbb{Z}_n $ diventa un grafo ad anello con 3n nodi, in cui ai nodi congrui a k mod 3 (k=0,1,2) attacco una fila di k ulteriori "nodi pendenti". Fatti tutti i gruppi ciclici che mi servono, li congiungo tra loro con delle "file" di lunghezza opportuna, come descritto sopra (ovviamente le file che congiungono gli anelli non hanno niente a che vedere con le file che definiscono il verso, spero sia chiaro). Per sicurezza, e per evitare casi banali fastidiosi (che non ho voglia di considerare uno per uno), faccio delle file sufficientemente lunghe, ovvero lunghe almeno 3.