The Twisted $D_{5,5}(q)$ Graph

One of the greatest discovery of in the theory of distance-regular graphs has been the twisted Grassmann graph by Edwin van Dam and Jack Koolen. Here I want to describe a small variation of their construction for the twisted $ {D_{5,5}(q)}$ graph. This post mostly to preserve my blackboard on the topic. (I tend to forget my blackboard talks over time.) It is also a nice throwback to my first blog post as it it will involve some diagram geometry.

The main topic is my paper about the twisted $ {D_{5,5}(q)}$ graph, published in Discrete Applied Mathematics. At the end I will also mention a preprint with Paulien Jansen, Linde Lambrecht, Yannick Neyt, Daan Rijpert, Hendrik Van Maldeghem, and Magali Victoor.

[I wanted to link a few more things in this blog post. Sadly, my VPN is not cooperating at the moment. Maybe I will add these later. Indeed, the fact that I need a VPN for WordPress.com, but not for my own domain, was the main reason for moving my blog.]

1. SRGs and DRGs

Many people know strongly regular graphs (SRGs). I have talked about SRGs very much on my blog, but let us repeat the definition. These are graphs on $ {v}$ vertices, not complete, not edgeless, such that every vertex has precisely $ {k}$ neighbors, any two adjacent vertices have precisely $ {\lambda}$ neighbors, and any two non-adjacent vertices have precisely $ {\mu}$ neighbors. One well-known example is the Petersen graph which has $ {(v, k, \lambda, \mu) = (10, 3, 0, 1)}$.

Strongly regular graphs are not very special. Many of them are known, for instance, I maintain a large selection of small examples here. Indeed, it can be argued that strongly regular graphs behave like random graphs and it seems plausible that almost all SRGs have no structure beyond its definition.

Distance-regular graphs are a natural generalization of this idea: A graph is distance-regular if there exist constants $ {p^i_{jk}}$ such that whenever we have vertices $ {x, y}$ at distance $ {i}$, then the number of vertices $ {z}$ at distance $ {j}$ from $ {x}$ and distance $ {k}$ from $ {y}$ is precisely $ {p^i_{jk}}$.

A strongly regular graph is a distance-regular with diameter $ {2}$. For large diameter, for a long time only a handful of examples where known:

1. Hamming graphs,
2. Johnson graphs,
3. Grassmann graphs,
4. Dual polar graphs,
5. Various graphs related to sesquilinear and quadratic forms.

These graphs are all very symmetric and, in particular, often distance-transitive and always vertex-transitive. If you are a group theorist (I am not), then you will inclined to think that any nice thing in life comes from a group. Thus, as far as I can tell, people believe that a classification of distance-regular graphs of sufficiently large diameter is plausible as all the known examples look nice. The discovery of the twisted Grassmann graphs (which we will describe below) made this endeavor at least much harder as the twisted Grassmann graphs are not vertex-transitive, but otherwise very similar to Grassmann graphs. Note that this is in some sense surprising as there are many classification results for Grassmann graphs. (For instance, see Sasha Gavrilyuk’s and Jack Koolen’s fantastic progress on that topic a few years ago here.)

2. Twisted Grassmann Graphs

The Grassmann graph $ {J_q(n, k)}$ has the $ {k}$-spaces of an $ {n}$-dimensional vector space $ {V}$ over the field with $ {q}$ elements as its vertices. Two vertices are adjacent when their meet has dimension $ {k-1}$. Sometimes it is nicer to use the dual description: The vertices are the $ {(n-k)}$-space in $ {V}$ and two of them are adjacent whenever their span has dimension $ {n-k+1}$. Starting with the Grassmann graph $ {\Gamma = J_q(2k+1, k+1)}$, the twisted Grassmann graph $ {\Gamma’}$ can be defined as follows:

1. Fix a hyperplane $ {H}$.
2. The vertices of $ {\Gamma’}$ are the the $ {(k+1)}$-space not in $ {H}$ and the $ {(k-1)}$-spaces in $ {H}$. This works numerically as the Gaussian (or $ {q}$-binomial) coefficient for the number of $ {(k+1)}$-spaces in $ {H}$ equals the number of $ {(k-1)}$-space in $ {H}$: $ {\genfrac{[}{]}{0pt}{}{2k}{k+1} = \genfrac{[}{]}{0pt}{}{2k}{k-1}}$.
3. Two $ {(k+1)}$-spaces are adjacent when their span is a $ {(k+2)}$-space (as in $ {\Gamma}$).
4. Two $ {(k-1)}$-spaces are adjacent when their meet is a $ {(k-2)}$-space (as in $ {J(2k, k-1)}$).
5. A $ {(k+1)}$-space and a $ {(k-1)}$-space are incident when the one is included in the other.

One needs to verify that $ {\Gamma’}$ is distance-regular and also not isomorphic with $ {\Gamma}$. Without going into much details, there is a beautiful diagram geometric way of seeing this. Recall that the Grassmannians have the following diagram of type $ {A_{n-1}}$:

What happens in the construction? We fix a hyperplane $ {H}$, so we look at the residue of $ {H}$. In the residue of $ {H}$, there is a symmetry (a polarity) which interchanges $ {j}$-spaces with $ {(2k-j)}$-space within $ {H}$. In particular, we flip the roles of the $ {(k+1)}$-spaces and $ {(k-1)}$-spaces in $ {H}$.

That is precisely we are doing. It requires a little bit of work to check that this gives a DRG. But the isomorphism part is intuitively clear: The polarity of $ {H}$ does not extend to a polarity (or any other symmetry) of $ {V}$. As the symmetries of $ {V}$ are essentially the symmetries of $ {\Gamma}$, we will obtain a non-isomorphic graph.

Can we generalize this? Yes, but sadly I only found one single other case! Strongly regular graphs which belong to the diagram of type $ {D_5}$.

3. The Twisted $ {D_{5,5}}$ graph

The $ {D_{5,5}}$-graph belongs to the following diagram of type $ {D_5}$:

PICTURE

Formally, the $ {D_{5,5}(q)}$ graph can be defined as follows:

1. You take the quadratic form $ {Q(x) = x_1x_2 + x_3x_4 + x_5x_6 + x_7x_8 + x_9x_{10}}$ on the vector space $ {V}$ of dimension $ {10}$ over the field with $ {q}$ elements.
2. With respect to $ {Q}$, some $ {5}$-spaces $ {S}$ of $ {V}$ are totally singular, that is, $ {Q(x) = 0}$ for all $ {x \in S}$. There are $ {2(q+1)(q^2+1)(q^3+1)(q^4+1)}$ of these. But they evenly split into two classes which we will call Greeks and Latins. Two totally singular $ {5}$-spaces of the same type meet in dimension $ {5}$, $ {3}$, or $ {1}$, two of different type meet in dimension $ {4}$, $ {2}$, or $ {0}$. Our vertices will be the $ {(q+1)(q^2+1)(q^3+1)(q^4+1)}$ Greeks.
3. We say that two Greeks are adjacent if they meet in a $ {3}$-space. This gives us the $ {D_{5,5}(q)}$ graph.

The $ {D_{5,5}(q)}$ has these parameters:

1. $v = (q+1)(q^2+1)(q^3+1)(q^4+1)$,
2. $k = q(q^2+1) \frac{q^5-1}{q-1}$,
3. $\lambda = q-1 + q^2(q+1)(q^2+q+1)$,
4. $\mu = (q^2+1)(q^2+q+1)$.

How does this look in the diagram?

Now what can we do to get a new strongly regular graph? We fix a totally singular $ {1}$-space $ {P}$. Then in the residue of $ {P}$ we find a polarity which interchanges Latins (through $ {P}$) and $ {2}$-spaces (through $ {P}$). Clearly, this symmetry of $ {D_4}$ does not extend to a symmetry of $ {D_5}$, so we can expect to get a non-isomorphic graph. Of course we can also describe this purely combinatorially: Take $ {\Gamma = D_{5,5}(q)}$. Construct the twisted $ {D_{5,5}(q)}$ graph $ {\Gamma’}$ as follows.

1. Fix a $ {1}$-space $ {P}$.
2. The vertices of $ {\Gamma’}$ are the the Latins not on $ {P}$ and the $ {2}$-spaces on $ {P}$.
3. Two Greeks are adjacent if they meet in a $ {3}$-space.
4. Two $ {2}$-spaces are adjacent if they span a totally singular $ {3}$-space.
5. A Greek and a $ {2}$-space are adjacent if their meet is a $ {1}$-space.

As a picture, this looks as follows:

This gives us a new family of strongly regular graphs. Here this is interesting as previously, the $ {D_{5,5}(q)}$ was the only strongly regular graph known with these parameters. Now we know a second family in form of the twisted $ {D_{5, 5}(q)}$. But, surely, there are many more!

4. Some Side-Product: Locally Characterized Graphs

Obviously, I was hoping to apply this method to more graphs. Sadly, I did not find any. But I was first hopeful for the $ {E_{6,1}(q)}$ graph which comes from an exceptional building of type $ {E_6}$:

For this I asked Hendrik Van Maldeghem about its properties. Apparently, everything failed, but we discussed that characterizing the graph by its local neighborhoods is surely possible. My questions inspired a spin-off with his research group which is currently under review. There we characterize $ {D_{5,5}(q)}$ and $ {E_{6,1}(q)}$ by its local structure. This is no constriction with the above as the twisted $ {D_{5,5}(q)}$ graph does not have the same local structure as $ {D_{5,5}(q)}$.

Finally, two more pictures of the Petersen graph which I drew while playing around on my tablet: