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.
> 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 X1 = (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 X2. Now consider the following graph Ω constructed from the incidence graph (X1 ∪X2, * ) by additionally joining two elements of X1 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 X1 and X1' 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 X2 be one of them and X2' be a copy of X2. Define incidence ~ for a∈X1, a' ∈X1', b ∈X2 and b' ∈X2', by
a~a' <=> { a, a' } is an edge of HoSi
a~b <=> a ∉b
a~b' <=> a ∈b'
a'~b <=> a' ∉b
a'~b' <=> a' ∉b'
b~b' <=> b ∩b' = emptyset
The geometry Γ(X1 ∪X1' ∪X2 ∪X2', ~) 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 := HoffmanSingletonGraph();
> 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 := MaximumClique(g);
> 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 ∈{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.
The Petersen graph, considered as a rank two coset geometry, can be implemented in the following way :
> g := Sym(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)
Maximal Parabolic Subgroups:
Permutation group g0 acting on a set of cardinality 5
Order = 12 = 2^2 * 3
(3, 4)
(1, 2)
(4, 5)
Permutation group g1 acting on a set of cardinality 5
Order = 8 = 2^3
(1, 2)
(3, 4)
(1, 3)(2, 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(8)|
> (1,2,3,4)(5,6,7,8), (1,5)(2,6)(3,7)(4,8), (2,4,5)(3,8,6)>;
> g0 := Stabilizer(g,1);
> g1 := Stabilizer(g,{1,2});
> g2 := Stabilizer(g,{1,2,3,4});
> 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)
Maximal Parabolic Subgroups:
Permutation group acting on a set of cardinality 8
Order = 8 = 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, 4, 5)(3, 8, 6)
(3, 6)(4, 5)
Permutation group acting on a set of cardinality 8
Order = 4 = 2^2
(1, 2)(3, 5)(4, 6)(7, 8)
(1, 2)(3, 4)(5, 6)(7, 8)
Type Set:
{@ 0, 1, 2 @}
The following lines of Magma-code construct a coset geometry of rank 6 for the group Sym(6).
> g := Sym(6);
> s := [Stabilizer(g,{1..j}) : j in {1..5}];
> cg := CosetGeometry(g,Set(s));
> cg;
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)
Maximal Parabolic Subgroups:
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 = 36 = 2^2 * 3^2
(1, 2)
(4, 5)
(5, 6)
(2, 3)
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 = 120 = 2^3 * 3 * 5
(1, 2)
(2, 3)
(3, 4)
(4, 5)
Type Set:
{@ 0, 1, 2, 3, 4 @}