OKlibrary  0.2.1.6
Chapter01.hpp File Reference

Chapter "Graphs" from [A Course in Combinatorics]. More...

Go to the source code of this file.

## Detailed Description

Chapter "Graphs" from [A Course in Combinatorics].

Documentation:

# On the automorphism group of the Petersen graph

• The Petersen graph is available as follows:
```kneser_g(5,2);
[{{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}},
{{{1,2},{3,4}},{{1,2},{3,5}},{{1,2},{4,5}},{{1,3},{2,4}},{{1,3},{2,5}},{{1,3},{4,5}},
{{1,4},{2,3}},{{1,4},{2,5}},{{1,4},{3,5}},{{1,5},{2,3}},{{1,5},{2,4}},{{1,5},{3,4}},
{{2,3},{4,5}},{{2,4},{3,5}},{{2,5},{3,4}}}]
petersen_graph();
?GRAPH
is_isomorphic(petersen_graph(), g2mg(kneser_g(5,2)));
true
```
• In the "grape"-package of GAP the Kneser-graphs are (likely incorrectly) called "JohnsonGraph"; for example
```> gap
gap> Size(AutGroupGraph(JohnsonGraph(5,2)));
120
gap> Size(AutGroupGraph(JohnsonGraph(40,2)));
815915283247897734345611269596115894272000000000
gap> Factorial(40);
815915283247897734345611269596115894272000000000
```
• Thus one expects the automorphism group of kneser_g(n,2) to be (naturally) isomorphic to the S_n ?!
• Investigating closer the automorphism group of the Petersen graph:
```gap> AutGroupGraph(JohnsonGraph(5,2));
Group([ (3,4)(6,7)(8,9), (2,3)(5,6)(9,10), (2,5)(3,6)(4,7), (1,2)(6,8)(7,9) ])
```
(note that GAP uses the cyle-representation of permutations).
• The corresponding permutations in list-form are
```t1 : [1,2,4,3,5,7,6,9,8,10]\$
t2 : [1,3,2,4,6,5,7,8,10,9]\$
t3 : [1,5,6,7,2,3,4,8,9,10]\$
t4 : [2,1,3,4,5,8,9,6,7,10]\$
```
Computing the closure, we see that this should be the S_5:
```length(closure_bydef_grd(transformation_l_compo, {t1,t2,t3,t4}));
120
```
• We need a nice proof (so that we *see*) that the automorphism group Aut(P) of the Petersen graph is actually S_5.
1. Via the faithful operation of S_5 we know that S_5 is a subgroup of Aut(P).
2. Exercise 2 in Section 4.6.4 of [Handbook of computational group theory] yields an argument.

# Preview on strongly regular graphs and projective plans

Exercise 1J is considered here.

Definition in file Chapter01.hpp.