Diagram of an Incidence Geometry#
As Francis Buekenhout defined it in [Buekenhout, 1979], the diagram of a firm, residually connected, flag–transitive geometry \(\Gamma\) is a complete graph \(K\), whose vertices are the elements of the set of types \(I\) of \(\Gamma\), provided with some additional structure which is further described as follows. To each vertex \(i \in I\), we attach the order \(s_i\) which is \(\mid \Gamma_F\mid - 1\) where \(F\) is any flag of type \(I\backslash\lbrace i\rbrace\), and the number \(n_i\) of elements of type \(i\) of \(\Gamma\). To every edge \(\lbrace i, j \rbrace\) of \(K\), we associate three positive integers \(d_{ij}\), \(g_{ij}\) and \(d_{ji}\) where \(g_{ij}\) (the gonality) is equal to half the girth of the incidence graph of a residue \(\Gamma_F\) of type \(\lbrace i,j \rbrace\), and \(d_{ij}\) (resp. \(d_{ji}\)), the i–diameter (resp. j–diameter) is the greatest distance from some fixed \(i\)–element (resp. \(j\)–element) to any other element in \(\Gamma_F\).
On a picture of the diagram, this structure will often be depicted as follows.
i d_ij g_ij d_ji j
O--------------------O
s_i-1 s_j-1
n_i n_j
Moreover, when \(g_{ij} = d_{ij} = d_{ji} = n \neq 2\), we only write \(g_{ij}\) and if \(n = 2\), we do not draw the edge \(\lbrace i,j \rbrace\).
- Diagram(D): IncGeom -> GrphUnd, GrphVertSet, GrphEdgeSet#
- Diagram(C): CosetGeom -> GrphUnd, GrphVertSet, GrphEdgeSet#
Given a firm, residually connected and flag–transitive incidence geometry \(D\) or a coset geometry \(C\), return a complete graph \(K\) whose vertices and edges are labelled in the following way. Every vertex \(i\) of \(K\) is labelled with a sequence of two positive integers, the first one being \(s_i\) and the second one being the number of elements of type \(i\) in \(D\). Every edge \(\lbrace i,j \rbrace\) is labelled with a sequence of three positive integers which are respectively \(d_{ij}\), \(g_{ij}\) and \(d_{ji}\).
Observe that both these functions do the same but the second one works much faster than the first one since it uses groups to compute the parameters of the diagram. So when the user has to compute the diagram of an incidence geometry, it is strongly advised that he first converts it into a coset geometry and then computes the diagram of the corresponding coset geometry.
- Example: diagram (ex-5b021d)#
Back to the Petersen graph : let us now explore a little more the first incidence geometry we constructed. Suppose that \(ig\) is the rank two incidence geometry corresponding to the Petersen graph. We may test whether it is firm, residually connected and flag–transitive.
> IsFirm(ig); true > IsRC(ig); true > IsFTGeometry(ig); true
Since it satisfies these three properties, we can compute its diagram.
> d, v, e := Diagram(ig); > d; Graph Vertex Neighbours 1 2 ; 2 1 ; > for x in v do print x, Label(x);end for; 1 [ 1, 10 ] 2 [ 2, 15 ] > for x in e do print x, Label(x);end for; {1, 2} [ 5, 5, 6 ]
We thus see that the diagram of \(ig\) can be drawn as follows.
1 5 5 6 2 O-------------------O 1 2 10 15
- Example: diagram (ex-ee5e4d)#
Back to the cube: let \(ig\) be the rank three incidence geometry of the cube as constructed above and compute its diagram.
> cube := IncidenceGeometry(g); > d, v, e := Diagram(cube); > d; Graph Vertex Neighbours 1 2 3 ; 2 1 3 ; 3 1 2 ; > for x in v do x, Label(x); end for; 1 [ 1, 8 ] 2 [ 1, 12 ] 3 [ 1, 6 ] > for x in e do x, Label(x); end for; {1, 2} [ 4, 4, 4 ] {1, 3} [ 2, 2, 2 ] {2, 3} [ 3, 3, 3 ]
So the diagram can be depicted as follows.
1 4 2 3 3 O-------------------O-------------------O 1 1 1 8 12 6
- Example: diagram (ex-cde392)#
Back to the Hoffman-Singleton graph:
> ig := IncidenceGeometry(HoffmanSingletonGraph()); > d, v, e := Diagram(ig); d; Graph Vertex Neighbours 1 2 ; 2 1 ; > for x in v do print x, Label(x); end for; 1 [ 1, 50 ] 2 [ 6, 175 ] > for x in e do print x, Label(x); end for; {1, 2} [ 5, 5, 6 ]
So the diagram can be depicted as follows.
1 5 5 6 2 O-------------------O 1 6 50 175
- Example: diagram (ex-3dd4a3)#
Back to Neumaier’s geometry : let \(ig\) be the rank four incidence geometry of Neumaier, as described above and compute its diagram.
> d, v, e := Diagram(neumaier); > d; Graph Vertex Neighbours 1 2 3 4 ; 2 1 3 4 ; 3 1 2 4 ; 4 1 2 3 ; > for x in v do print x, Label(x); end for; 1 [ 2, 50 ] 2 [ 2, 50 ] 3 [ 2, 50 ] 4 [ 2, 50 ] > for x in e do print x, Label(x); end for; {1, 2} [ 4, 4, 4 ] {1, 3} [ 2, 2, 2 ] {1, 4} [ 3, 3, 3 ] {2, 3} [ 3, 3, 3 ] {2, 4} [ 2, 2, 2 ] {3, 4} [ 4, 4, 4 ]
So the diagram can be depicted as follows.
. 1 4 2 . 2 O-----------------O 2 . 50 | | 50 . | | . | | . 3 | | 3 . | | . | | . | 4 | . 3 O-----------------O 4 . 2 2 . 50 50