Construct the incidence geometry IG having as incidence graph the (labelled) graph G.
If G is an unlabelled graph, then the set of elements of IG is the set of vertices and edges of G, the set of types is {@ 1, 2 @} where elements of type 1 are vertices of G and elements of type 2 are edges of G. An element x of type 1 is incident to an element y of type 2 iff the vertex x in G is on the edge y of G.
If G is a labelled graph, i.e. a graph whose vertices have labels, then the set of elements of IG is the set of vertices of G, the set of types is the set of labels of the vertices of G and the incidence graph is G. The function returns one value: the incidence geometry IG.
Construct the incidence geometry IG from the coset geometry C. This is done using Tits' algorithm described in the introduction of this chapter. The function returns one value: the incidence geometry IG.
> gr := Graph<10|
> {1,2},{1,5},{1,6},{2,7},{2,3},{3,8},{3,4},{4,9},{4,5},{5,10},
> {6,8},{8,10},{10,7},{7,9},{9,6}>;
> ig := IncidenceGeometry(gr);
> ig;
Incidence geometry ig with 2 types and with underlying graph:
Graph
Vertex Neighbours
1 11 12 13 ;
2 11 14 15 ;
3 14 16 17 ;
4 16 18 19 ;
5 12 18 20 ;
6 13 21 22 ;
7 15 23 24 ;
8 17 21 25 ;
9 19 22 23 ;
10 20 24 25 ;
11 1 2 ;
12 1 5 ;
13 1 6 ;
14 2 3 ;
15 2 7 ;
16 3 4 ;
17 3 8 ;
18 4 5 ;
19 4 9 ;
20 5 10 ;
21 6 8 ;
22 6 9 ;
23 7 9 ;
24 7 10 ;
25 8 10 ;
> g := Graph<26|
> {1,9},{1,12},{1,13},{1,21},{1,22},{1,25},
> {2,9},{2,10},{2,14},{2,21},{2,22},{2,23},
> {3,10},{3,11},{3,15},{3,21},{3,23},{3,24},
> {4,11},{4,12},{4,16},{4,21},{4,24},{4,25},
> {5,13},{5,18},{5,17},{5,22},{5,25},{5,26},
> {6,14},{6,19},{6,18},{6,23},{6,22},{6,26},
> {7,15},{7,19},{7,20},{7,24},{7,26},{7,23},
> {8,17},{8,20},{8,16},{8,26},{8,24},{8,25},
> {9,21},{9,22},{10,21},{10,23},{11,21},{11,24},
> {12,21},{12,25},{13,22},{13,25},{14,22},{14,23},
> {15,23},{15,24},{16,24},{16,25},{17,25},{17,26},
> {18,22},{18,26},{19,23},{19,26},{20,24},{20,26}>;
> v := VertexSet(g);
> AssignLabels(v,[1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3]);
> cube := IncidenceGeometry(g);
> cube;
Incidence geometry cube with 3 types and with underlying graph:
Graph
Vertex Neighbours
1 9 12 13 21 22 25 ;
2 9 10 14 21 22 23 ;
3 10 11 15 21 23 24 ;
4 11 12 16 21 24 25 ;
5 13 17 18 22 25 26 ;
6 14 18 19 22 23 26 ;
7 15 19 20 23 24 26 ;
8 16 17 20 24 25 26 ;
9 1 2 21 22 ;
10 2 3 21 23 ;
11 3 4 21 24 ;
12 1 4 21 25 ;
13 1 5 22 25 ;
14 2 6 22 23 ;
15 3 7 23 24 ;
16 4 8 24 25 ;
17 5 8 25 26 ;
18 5 6 22 26 ;
19 6 7 23 26 ;
20 7 8 24 26 ;
21 1 2 3 4 9 10 11 12 ;
22 1 2 5 6 9 13 14 18 ;
23 2 3 6 7 10 14 15 19 ;
24 3 4 7 8 11 15 16 20 ;
25 1 4 5 8 12 13 16 17 ;
26 5 6 7 8 17 18 19 20 ;
Start with the set X_1 = (7 choose 3) of all triples from 7. There are 30 collections of 7 triples that form the lines of a Fano plane with point set 7. The group Sym(7) acts transitively on this set of 30 elements, but the alternating group Alt(7) has two orbits, of cardinality 15 each. Select one and call it X_2. Now consider the following graph Omega constructed from the incidence graph (X_1 union X_2, * ) by additionally joining two elements of X_1 whenever they have empty intersection. The following lines of Magma-code implement the Hoffman-Singleton graph as an incidence geometry of rank 2. We will study it more later.
> HoffmanSingletonGraph := function()
> pentagram := Graph< 5 | { {1,3}, {3,5}, {5,2}, {2,4}, {4,1} } >;
> pentagon := PolygonGraph(5);
> PP := pentagram join pentagon;
> HS := &join [ PP : i in [1..5] ];
> return HS + { { Vertices(HS) | i + j*10, k*10 + 6 + (i+j*k) mod 5 } : > i in [1..5], j in [0..4], k in [0..4] };
> end function;
> ig := IncidenceGeometry(HoffmanSingletonGraph());
Take X_1 and X_(1') to be two copies of the vertex set of HoSi. The group Sym(7) acts transitively on the set of maximal cocliques of HoSi. The subgroup Alt(7) has two orbits of size 15 each. Let X_2 be one of them and X_(2') be a copy of X_2. Define incidence ~ for a in X_1, a' in X_(1'), b in X_2 and b' in X_(2'), by
a~a' Leftrightarrow { a, a' } is an edge of HoSi
a~b Leftrightarrow a notin b
a~b' Leftrightarrow a in b'
a'~b Leftrightarrow a'notin b
a'~b' Leftrightarrow a'notin b'
b~b' Leftrightarrow bintersect b' = emptyset
The geometry Gamma(X_1union X_(1')union X_2union X_(2'), ~) is the Neumaier geometry. The following lines of Magma-code implement this geometry as a rank four incidence geometry. We assume that ig is the incidence geometry corresponding to the Hoffman-Singleton graph, as described in the previous example.
> gr := Graph<10|
> {1,2},{1,5},{1,6},{2,7},{2,3},{3,8},{3,4},{4,9},{4,5},{5,10},
> {6,8},{8,10},{10,7},{7,9},{9,6}>;
> ig := IncidenceGeometry(gr);
> aut := AutomorphismGroup(ig);
> n := NormalSubgroups(aut);
> X1 := VertexSet(gr);
> g := CompleteGraph(50);
> e := EdgeSet(gr);
> ebis := [];
> for x in EdgeSet(gr) do
> for i := 1 to 50 do
> for j := i+1 to 50 do
> if VertexSet(gr)!i in x then
> if VertexSet(gr)!j in x then
> Append( ebis,[i,j]);
> end if;
> end if;
> end for;
> end for;
> end for;
> for i := 1 to #ebis do
> RemoveEdge( g,ebis[i][1],ebis[i][2]);
> end for;
> c := Clique(g,15);
> cbis := [];
> for i := 1 to 50 do
> if (VertexSet(gr)!i in c) then Append( cbis,i); end if;
> end for;
> c := Set(cbis);
> X2 := Orbit(n[2]`subgroup,c);
> X2 := SetToSequence(X2);
> e := [];
> for i := 1 to 50 do
> for j := 1 to 50 do
> if X1!i in Neighbours(X1!j) then Append( e,{i,j+50}); end if;
> end for;
> end for;
> for i :=1 to 50 do
> for j := 1 to 50 do
> if not(i in X2[j]) then Append( e,{i,j+100});end if;
> end for;
> end for;
> for i :=1 to 50 do
> for j := 1 to 50 do
> if i in X2[j] then Append( e,{i,j+150});end if;
> end for;
> end for;
> for i :=1 to 50 do
> for j := 1 to 50 do
> if i in X2[j] then Append( e,{i+50,j+100});end if;
> end for;
> end for;
> for i :=1 to 50 do
> for j := 1 to 50 do
> if not(i in X2[j]) then Append( e,{i+50,j+150});end if;
> end for;
> end for;
> for i :=1 to 50 do
> for j := 1 to 50 do
> if X2[i] meet X2[j] eq {} then Append( e,{i+100,j+150});end if;
> end for;
> end for;
> gr2 := Graph<200|Set(e)>;
> v := VertexSet(gr2);
> labs := [i: j in {1..50}, i in {1..4}];
> AssignLabels(v,labs);
> neumaier := IncidenceGeometry(gr2);
Construct the coset geometry CG with set of types I, obtained from the group G and the set S of subgroups of G. The sets S and I must have same cardinality.
If G is a permutation group and S is a set of subgroups of G, the corresponding coset geometry, obtained by using Tits' algorithm (see above) is constructed. If S and I are indexed sets, then the cosets of the subgroup S[i] are elements of type I[i], for all i in {0, ..., n - 1} where n is the cardinality of S (and I). The function returns one value: the coset geometry CG.
Construct the coset geometry CG obtained from the group G and the set S of subgroups of G.
If G is a permutation group and S is a set of subgroups of G, the corresponding coset geometry, obtained by using Tits' algorithm (see above) is constructed. To every subgroup in S is associated a number from 0 to n - 1 where n is the cardinality of S. The function returns one value: the coset geometry CG.
Convert the incidence geometry D into a coset geometry.
If D is an incidence geometry that can be converted into a coset geometry, the coset geometry isomorphic to it is constructed in the following way. The group G of the coset geometry CG is the automorphism group of D. Magma determines a chamber C of D, that is a clique of the incidence graph of D containing one element of each type. To every element x in C, Magma associates a subgroup G_x which is the stabilizer of x in G. The subgroups (G_x, x in C) are the maximal parabolic subgroups of CG. In order to obtain a coset geometry combinatorially isomorphic to the incidence geometry we started with, the group G must be transitive on every rank two truncation of D. If this condition is satisfied, the function returns a boolean set to the value true and the coset geometry CG. Otherwise, the function returns false.
The Petersen graph, considered as a rank two coset geometry, can be implemented in the following way :
> g := Sym(GrpPerm,5);
> g0 := Stabilizer(g,{1,2});
> g01 := Stabilizer(g,[{1,2},{3,4}]);
> g1 := sub<g|g01,(1,3)(2,4)>;
> cg := CosetGeometry(g,{g0,g1});
> cg;
Coset geometry cg with 2 types
Group:
Symmetric group g acting on a set of cardinality 5
Order = 120 = 2^3 * 3 * 5
(1, 2, 3, 4, 5)
(1, 2)
Subgroups:
Permutation group acting on a set of cardinality 5
Order = 120 = 2^3 * 3 * 5
(1, 2, 3, 4, 5)
(1, 2)
Permutation group acting on a set of cardinality 5
Order = 12 = 2^2 * 3
(3, 5)
(1, 2)
(3, 4)
Permutation group acting on a set of cardinality 5
Order = 2^3
(1, 3)(2, 4)
(3, 4)
Permutation group acting on a set of cardinality 5
Order = 2^2
(1, 2)
(3, 4)
Type Set:
{@ 0, 1 @}
The rank three geometry consisting of the vertices, edges and faces of the cube, can be implemented as a coset geometry in the following way, which is much easier than having to give the full incidence graph :
> g := sub<Sym(GrpPerm,8)|
> (1,2,3,4)(5,6,7,8), (1,5)(2,6)(3,7)(4,8), (2,4,5)(3,8,6)>;
> #g;
> g0 := Stabilizer(g,1);
> g0;
> g1 := Stabilizer(g,{1,2});
> g1;
> g2 := Stabilizer(g,{1,2,3,4});
> g2;
> cg := CosetGeometry(g,{g0,g1,g2});
> cg;
Coset geometry cg with 3 types
Group:
Permutation group g acting on a set of cardinality 8
Order = 48 = 2^4 * 3
(1, 2, 3, 4)(5, 6, 7, 8)
(1, 5)(2, 6)(3, 7)(4, 8)
(2, 4, 5)(3, 8, 6)
Subgroups:
Permutation group acting on a set of cardinality 8
Order = 48 = 2^4 * 3
(1, 2, 3, 4)(5, 6, 7, 8)
(1, 5)(2, 6)(3, 7)(4, 8)
(2, 4, 5)(3, 8, 6)
Permutation group acting on a set of cardinality 8
Order = 2^3
(1, 2)(3, 4)(5, 6)(7, 8)
(2, 4)(6, 8)
Permutation group acting on a set of cardinality 8
Order = 6 = 2 * 3
(2, 5)(3, 8)
(3, 6)(4, 5)
Permutation group acting on a set of cardinality 8
Order = 2
(2, 4)(6, 8)
Permutation group acting on a set of cardinality 8
Order = 2^2
(1, 2)(3, 5)(4, 6)(7, 8)
(1, 2)(3, 4)(5, 6)(7, 8)
Permutation group acting on a set of cardinality 8
Order = 2
(1, 2)(3, 4)(5, 6)(7, 8)
Permutation group acting on a set of cardinality 8
Order = 2
(3, 6)(4, 5)
Permutation group acting on a set of cardinality 8
Order = 1
Type Set:
{@ 0, 1, 2 @}
We can then convert it into an incidence geometry by typing the following command and obtain the same incidence geometry as described in the example for incidence geometries.
> ig := IncidenceGeometry(cg); > ig; Incidence geometry ig with 3 types and with underlying graph: Graph Vertex Neighbours 1 7 8 10 11 15 18 19 20 ; 2 8 11 12 14 20 21 22 24 ; 3 7 8 9 12 15 16 23 24 ; 4 7 9 10 13 16 17 18 25 ; 5 9 12 13 14 17 22 23 26 ; 6 10 11 13 14 19 21 25 26 ; 7 1 3 4 15 16 18 ; 8 1 2 3 15 20 24 ; 9 3 4 5 16 17 23 ; 10 1 4 6 18 19 25 ; 11 1 2 6 19 20 21 ; 12 2 3 5 22 23 24 ; 13 4 5 6 17 25 26 ; 14 2 5 6 21 22 26 ; 15 1 3 7 8 ; 16 3 4 7 9 ; 17 4 5 9 13 ; 18 1 4 7 10 ; 19 1 6 10 11 ; 20 1 2 8 11 ; 21 2 6 11 14 ; 22 2 5 12 14 ; 23 3 5 9 12 ; 24 2 3 8 12 ; 25 4 6 10 13 ; 26 5 6 13 14 ;
The following lines of Magma-code construct a coset geometry of rank 6 for the group Sym(6).
> g := Sym(GrpPerm,6);
> s := [Stabilizer(g,{1..j}) : j in {1..5}];
> cg := CosetGeometry(g,Set(s));
Coset geometry cg with 5 types
Group:
Symmetric group g acting on a set of cardinality 6
Order = 720 = 2^4 * 3^2 * 5
(1, 2, 3, 4, 5, 6)
(1, 2)
Subgroups:
Permutation group acting on a set of cardinality 6
Order = 720 = 2^4 * 3^2 * 5
(1, 2, 3, 4, 5, 6)
(1, 2)
Permutation group acting on a set of cardinality 6
Order = 48 = 2^4 * 3
(3, 4)
(4, 5)
(5, 6)
(1, 2)
Permutation group acting on a set of cardinality 6
Order = 48 = 2^4 * 3
(1, 2)
(2, 3)
(3, 4)
(5, 6)
Permutation group acting on a set of cardinality 6
Order = 2^3
(1, 2)
(3, 4)
(5, 6)
Permutation group acting on a set of cardinality 6
Order = 36 = 2^2 * 3^2
(4, 6)
(1, 3)
(1, 2)
(4, 5)
Permutation group acting on a set of cardinality 6
Order = 12 = 2^2 * 3
(4, 6)
(1, 2)
(4, 5)
Permutation group acting on a set of cardinality 6
Order = 12 = 2^2 * 3
(1, 3)
(1, 2)
(5, 6)
Permutation group acting on a set of cardinality 6
Order = 2^2
(1, 2)
(5, 6)
Permutation group acting on a set of cardinality 6
Order = 120 = 2^3 * 3 * 5
(2, 3)
(3, 4)
(4, 5)
(5, 6)
Permutation group acting on a set of cardinality 6
Order = 24 = 2^3 * 3
(3, 4)
(4, 5)
(5, 6)
Permutation group acting on a set of cardinality 6
Order = 12 = 2^2 * 3
(2, 3)
(3, 4)
(5, 6)
Permutation group acting on a set of cardinality 6
Order = 2^2
(3, 4)
(5, 6)
Permutation group acting on a set of cardinality 6
Order = 12 = 2^2 * 3
(4, 5)
(2, 3)
(5, 6)
Permutation group acting on a set of cardinality 6
Order = 6 = 2 * 3
(4, 6)
(4, 5)
Permutation group acting on a set of cardinality 6
Order = 2^2
(2, 3)
(5, 6)
Permutation group acting on a set of cardinality 6
Order = 2
(5, 6)
Permutation group acting on a set of cardinality 6
Order = 120 = 2^3 * 3 * 5
(1, 2)
(2, 3)
(3, 4)
(4, 5)
Permutation group acting on a set of cardinality 6
Order = 12 = 2^2 * 3
(3, 4)
(1, 2)
(4, 5)
Permutation group acting on a set of cardinality 6
Order = 24 = 2^3 * 3
(1, 2)
(2, 3)
(3, 4)
Permutation group acting on a set of cardinality 6
Order = 2^2
(1, 2)
(3, 4)
Permutation group acting on a set of cardinality 6
Order = 12 = 2^2 * 3
(1, 2)
(2, 3)
(4, 5)
Permutation group acting on a set of cardinality 6
Order = 2^2
(1, 2)
(4, 5)
Permutation group acting on a set of cardinality 6
Order = 6 = 2 * 3
(1, 3)
(1, 2)
Permutation group acting on a set of cardinality 6
Order = 2
(1, 2)
Permutation group acting on a set of cardinality 6
Order = 24 = 2^3 * 3
(2, 3)
(3, 4)
(4, 5)
Permutation group acting on a set of cardinality 6
Order = 6 = 2 * 3
(3, 5)
(3, 4)
Permutation group acting on a set of cardinality 6
Order = 6 = 2 * 3
(2, 3)
(3, 4)
Permutation group acting on a set of cardinality 6
Order = 2
(3, 4)
Permutation group acting on a set of cardinality 6
Order = 2^2
(2, 3)
(4, 5)
Permutation group acting on a set of cardinality 6
Order = 2
(4, 5)
Permutation group acting on a set of cardinality 6
Order = 2
(2, 3)
Permutation group acting on a set of cardinality 6
Order = 1
Type Set:
{@ 0, 1, 2, 3, 4 @}
Taking back the last example for incidence geometries, we can convert the Neumaier geometry into a coset geometry by typing the following command (neumaier is the Neumaier geometry constructed above):
> ok,cg := CosetGeometry(neumaier);
> ok; true
This means the conversion has been done successfully. So cg is the coset geometry corresponding to neumaier.
> cg; Coset geometry cg with 4 types Group: Permutation group acting on a set of cardinality 200 Order = 126000 = 2^4 * 3^2 * 5^3 * 7 Subgroups: Permutation group acting on a set of cardinality 200 Order = 126000 = 2^4 * 3^2 * 5^3 * 7 Permutation group acting on a set of cardinality 200 Order = 2520 = 2^3 * 3^2 * 5 * 7 Permutation group acting on a set of cardinality 200 Order = 2520 = 2^3 * 3^2 * 5 * 7 Permutation group acting on a set of cardinality 200 Order = 72 = 2^3 * 3^2 Permutation group acting on a set of cardinality 200 Order = 2520 = 2^3 * 3^2 * 5 * 7 Permutation group acting on a set of cardinality 200 Order = 360 = 2^3 * 3^2 * 5 Permutation group acting on a set of cardinality 200 Order = 168 = 2^3 * 3 * 7 Permutation group acting on a set of cardinality 200 Order = 24 = 2^3 * 3 Permutation group acting on a set of cardinality 200 Order = 2520 = 2^3 * 3^2 * 5 * 7 Permutation group acting on a set of cardinality 200 Order = 168 = 2^3 * 3 * 7 Permutation group acting on a set of cardinality 200 Order = 360 = 2^3 * 3^2 * 5 Permutation group acting on a set of cardinality 200 Order = 24 = 2^3 * 3 Permutation group acting on a set of cardinality 200 Order = 72 = 2^3 * 3^2 Permutation group acting on a set of cardinality 200 Order = 24 = 2^3 * 3 Permutation group acting on a set of cardinality 200 Order = 24 = 2^3 * 3 Permutation group acting on a set of cardinality 200 Order = 2^3 Type Set: {@ 1, 2, 3, 4 @}