Archive for May, 2009

a subgeometry of D_3-dual polar space

29 May, 2009

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)…

D3-dual polar space is a bipartite graph \Gamma=(V,E) that satisfies the following properties:

  • each 2-path lies in a unique complete bipartite subgraph Q with parts of size \geq 3;
  • for any vertex v\in V the edges (v,u)\in E and the subgraphs Q\ni v form a projective plane \Pi_v, with respect to inclusion.

So from the point of view of Tits’ “local” approach to buildings we talk about a “geometry with diagram” \circ==\circ--\circ, where \circ==\circ stands for a generalised 4-gon (and indeed complete bipartite graph is a trivial example of such a thing), and \circ--\circ 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 \Pi_v being of order q=3. Then we have a distance-regular graph of diameter 3, with distribution diagram around a vertex as follows:
So each vertex v has 13 neighbours, 39 vertices at distance 2, and 27 at distance 3; each neighbour of v has 12 neighbours at distance 2 from v, each distance 2 vertex has 4 mutual neighbours with v, and 9 neighbours at distance 3 from v.

Such a graph is unique: this is so for each q 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 \Gamma, and subgraphs Q as lines, with adjacency between lines and points (resp. planes) being inclusion.
And k-dimensional finite projective spaces, for k\geq 3, are all coming from the natural construction from the 4-dimensional vector space over a Galois field.

Another natural construction of \Gamma comes from a non-degenerate 6-variate quadratic form, over \mathbb{F}_q, 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 U is called totally isotropic w.r.t. to a form \langle , \rangle if \langle s , t \rangle=0 for all s,t\in U.
Then the vertices of \Gamma 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 q=3 one can take \langle X,X\rangle=X_1 X_2-X_3^2-X_4^2-X_5^2-X_6^2, and a maximal totally isotropic subspace with a basis
\{(1,0,\dots,0), (0,0,0,1,1,1),  (0,0,1,1,-1,0)\}.
The advantage of this construction is that it allows to describe dual polar graphs D_k for k\geq 4 as well. (Take 2k-variate nondeg. form of maximal Witt index equal to k, etc.)

We are interested in constructing a subgraph \Delta of \Gamma that behaves
like \Gamma when we look at the neighbours of v, with the difference that edges on v and the subgraphs Q on v now form an affine plane, not a projective one. So Q\cap\Delta \cong K_{q,q}, while Q\cong K_{q+1,q+1}. In order to do so, we pick up an edge (s,t)\in E\Gamma, and remove from the latter all the vertices adjacent to either s or t. The resulting graph is exactly \Delta that we want!
In terms of maximal totally isotropic subspaces, the vertices of \Delta are these ones that have 0 intersection with the 2-dimensional subspace corresponding to the intersection of the 3-dimensional subspaces corresponding to s and t. We have a distance-regular graph of diameter 4, with distribution diagram (for q=3) around a vertex as follows:
It is a q-fold antipodal cover of K_{q^2,q^2}, i.e. the vertices are partitioned into sets of size q 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.