In 1991 I provided to Andries Brouwer more examples of distance-regular graphs that were not known at the time the book “Distance-regular graphs” by Andries, A.M.Cohen, and A.Neumaier, that he included into “Additions and corrections”. Recently I was asked for more details on these. So I started to recall what that was all about (I drifted quite far from that area of research since then, I must say)…

D_{3}-dual polar space is a bipartite graph that satisfies the following properties:

- each 2-path lies in a unique complete bipartite subgraph with parts of size
- for any vertex the edges and the subgraphs form a projective plane with respect to inclusion.

So from the point of view of Tits’ “local” approach to buildings we talk about a “geometry with diagram” where stands for a generalised 4-gon (and indeed complete bipartite graph is a trivial example of such a thing), and stands for a generalised 3-gon, i.e., a projective plane.

To construct a typical example, let us consider the case of the projective planes being of order Then we have a distance-regular graph of diameter 3, with distribution diagram around a vertex as follows:

[1]^{13}—^{1}[13]^{12}—^{4}[39]^{9}—^{13}[27]

So each vertex has 13 neighbours, 39 vertices at distance 2, and 27 at distance 3; each neighbour of has 12 neighbours at distance 2 from each distance 2 vertex has 4 mutual neighbours with and 9 neighbours at distance 3 from

Such a graph is unique: this is so for each a prime power, in fact, there is 1-to-1 correspondence between such graphs and 3-dimensional projective spaces: take as *points* (resp. *planes*) of the space parts of the bipartition, with incidence being the adjacency in and subgraphs as *lines*, with adjacency between *lines* and *points* (resp. *planes*) being inclusion.

And -dimensional finite projective spaces, for are all coming from the natural construction from the 4-dimensional vector space over a Galois field.

Another natural construction of comes from a non-degenerate 6-variate quadratic form, over of maximal Witt index (i.e. a form that cannot be rewritten as a form with lesser number of variables using a nondeg. linear transformation, and such that there are totally isotropic subspaces of dimension 3, the maximal possible in fact). Recall that a subspace is called totally isotropic w.r.t. to a form if for all

Then the vertices of are the maximal totally isotropic subspaces, with adjacency being the maximality of the intersection dimension (i.e. two vertices are adjacent iff the corresponding 3-spaces intersect in a 2-dimensional subspace).

** Example.** For one can take and a maximal totally isotropic subspace with a basis

The advantage of this construction is that it allows to describe dual polar graphs for as well. (Take -variate nondeg. form of maximal Witt index equal to , etc.)

We are interested in constructing a subgraph of that behaves

like when we look at the neighbours of with the difference that edges on and the subgraphs on now form an affine plane, not a projective one. So while In order to do so, we pick up an edge and remove from the latter all the vertices adjacent to either or The resulting graph is exactly that we want!

In terms of maximal totally isotropic subspaces, the vertices of are these ones that have 0 intersection with the 2-dimensional subspace corresponding to the intersection of the 3-dimensional subspaces corresponding to and We have a distance-regular graph of diameter 4, with distribution diagram (for ) around a vertex as follows:

[1]^{9}—^{1}[9]^{8}—^{3}[24]^{6}—^{8}[18]^{1}—^{9}[2]

It is a fold antipodal cover of , i.e. the vertices are partitioned into sets of size such that pairwise distances between vertices in each of them are maximal, i.e. 4, and there is a naturally defined structure of complete bipartite graphs on them.

Tags: maths

## Leave a Reply