Construction of Incidence and Coset Geometries#
Construction of an Incidence Geometry#
- IncidenceGeometry(G): GrphUnd -> IncGeom#
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 \(\lbrace @ 1,2 @\rbrace\) 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\).
- Example: Constructors (ex-a2453c)#
The Petersen graph, considered as a rank two incidence geometry, may be constructed by the following statement:
> 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 ;
- Example: Constructors (ex-2bc35f)#
The rank three geometry consisting of the vertices, edges and faces of the cube, with symmetric inclusion as incidence might be encoded in the following way. The first 8 vertices of the graph correspond to the vertices of the cube, the next 12 vertices correspond to the edges of the cube and the last 6 are the faces of the cube.
> 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 ;
- Example: Constructors (ex-65148f)#
The Hoffman-Singleton graph \(HoSi\) : the following description is taken from the book Diagram Geometry, by A. Cohen and F. Buekenhout [Buekenhout and Cohen, In preparation].
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 \cup 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());
- Example: Constructors (ex-666366)#
A rank four geometry constructed from the Hoffman-Singleton graph : the following description is taken from the book Diagram Geometry, by A. Cohen and F. Buekenhout.
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 \(\sim\) for \(a\in X_1\), \(a' \in X_{1'}\), \(b \in X_2\) and \(b' \in X_{2'}\), by
\(a\sim a' \Leftrightarrow \lbrace a,a'\rbrace\) is an edge of \(HoSi\)
\(a\sim b \Leftrightarrow a \notin b\)
\(a\sim b' \Leftrightarrow a \in b'\)
\(a'\sim b \Leftrightarrow a' \notin b\)
\(a'\sim b' \Leftrightarrow a' \notin b'\)
\(b\sim b' \Leftrightarrow b \cap b' = \emptyset\)
The geometry \(\Gamma(X_1 \cup X_{1'} \cup X_2 \cup X_{2'},\sim)\) 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);
Construction of a Coset Geometry#
- CosetGeometry(G, S, I): GrpPerm, Set, Set -> CosetGeom#
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, \ldots, n-1\}\) where \(n\) is the cardinality of \(S\) (and \(I\)). The function returns one value: the coset geometry \(CG\).
- CosetGeometry(G, S): GrpPerm, Set -> CosetGeom#
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\).
- Example: Constructors (ex-a1eb9c)#
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 @}
- Example: Constructors (ex-4a5ca3)#
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 @}
- Example: Constructors (ex-16511c)#
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 @}