## 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:
[1]131[13]124[39]913[27]
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:
[1]91[9]83[24]68[18]19[2]
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.