# 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: ```magma > 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. ```magma > 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](../../references.md#cite-buekcohen)]. 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. ```magma > 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. ```magma > 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 : ```magma > g := Sym(5); > g0 := Stabilizer(g,{1,2}); > g01 := Stabilizer(g,[{1,2},{3,4}]); > g1 := sub; > 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 : ```magma > g := sub (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)$. ```magma > 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 @} ```