Strongly Regular Grassmann Graphs
I would like to determine the parameters of the Grassmann graphs that are strongly regular. To this end, my primary goal is to verify that:
- For all natural numbers \(n \geq 4\) and prime powers \(q\), the Grassmann graph \(J_q(n,2)\) is an \(\operatorname{SRG}\left ( {n \brack 2}_{q}, q {2 \brack 1}_{q} {n - 2 \brack 1}_{q} , \left ( q {n - 2 \brack 1}_{q} - 1 \right ) + q^{2}, \left ( {2 \brack 1}_{q} \right )^{2} \right)\).
Suppose that we are given an arbitrary natural number \(n \geq 4\) and prime power \(q\). Let \(S = \{ W : W \leq V \operatorname{and} \operatorname{dim}{W} = 2 \}\) denote the set of all subspaces of dimension \(2\) of a vector space \(V\) of dimension \(n\) over the finite field \(\mathbb{F}_{q}\) of order \(q\). Consider the simple graph \(G = \left ( S, E \right )\) formed with the set \(S\) as vertices and the set \(E = \{ \{W, Z\} : W, Z \in S \operatorname{and} \operatorname{dim}(W \cap Z) = 1 \}\) as edges. Then:
-
Select an arbitrary \(W \in S\), select an arbitrary one-dimensional subspace \(L\) of \(W\), and let \(S_{W, L} = \{ X : X \in S \operatorname{and} {X \cap W} = L \}\) denote the subset of \(S\) of two-dimensional subspaces of \(V\) that share exactly \(L\) in common with \(W\). Select an arbitrary \(Y \in S_{W,L}\): since \(\left\vert{Y \setminus L}\right\vert = \left\vert{Y}\right\vert - \left\vert{L}\right\vert = q^{2} - q\) and \(\left ( Y \setminus L \right ) \subseteq \left ( V \setminus W \right )\), we have that \(\left\vert\{ v : v \in \left ( V \setminus W \right ) \operatorname{and} Y = L \oplus \operatorname{span}\{v\} \} \right\vert = q^{2} - q\), which is independent of our choice of \(Y\). This means here that for each of the \(\left\vert{V \setminus W}\right\vert = q^{n} - q^{2}\) ways to select a non-zero vector in \(v \in \left(V \setminus W\right)\) in order to construct a two-dimensional subspace \(Y = L \oplus \operatorname{span}\{v\} \in S_{W,L}\), there will be a total of \(q^{2} - q\) elements of \(\left(V \setminus W\right)\) that could be selected to construct the same subspace \(Y \in S_{W, L}\) in this way. It is then possible to deduce that \(\left\vert{S_{W, L}}\right\vert = \frac{q^{n} - q^{2}}{q^{2} - q} = q {n - 2 \brack 1}_{q}\), which is independent of our particular choices of \(W\) and \(L\). Therefore the number of two-dimensional subspaces of \(V\) that share exactly a particular one-dimensional subspace of \(V\) in common with a particular two-dimensional subspace of \(V\) is given in general by \(q {n - 2 \brack 1}_{q}\), independent of particular choices of a one-dimensional subspace and a two-dimensional subspace of \(V\); I will make use of this fact in the next two steps towards achieving my goal for this post.
-
Select an arbitrary \(W \in S\), and let \(N(W)\) denote the neighbourhood of \(W\) on \(G\). Then there are \({2 \brack 1}_{q}\) ways to select a one-dimensional subspace of \(W\), and for each one-dimensional subspace \(L\) of \(W\), we have from my previous point that \(\left\vert{S_{W, L}}\right\vert = \left\vert{\{ X : X \in S \operatorname{and} {X \cap W} = L\}}\right\vert = q {n - 2 \brack 1}_{q}\) other two-dimensional subspaces of \(V\) in \(S\) that share exactly \(L\) in common with \(W\). It is then possible to deduce that \(\left\vert{N(W)}\right\vert = {2 \brack 1}_{q} \left ( q {n - 2 \brack 1}_{q} \right ) = q {2 \brack 1}_{q} {n - 2 \brack 1}_{q}\), which is independent of \(W\). Therefore \(G\) in this context is \(q {2 \brack 1}_{q} {n - 2 \brack 1}_{q}\)-regular.
-
Select an arbitrary \(\{W, X \} \in E\), and let \(L = W \cap X\). Additionally, let \(T = N(W) \cap N(X)\), where \(N(W)\) and \(N(X)\) denote the respective neighbourhoods of \(W\) and \(X\) on \(G\). Partition \(T = T_1 \sqcup T_2\) into disjoint subsets \(T_1 = \{ Z : Z \in \left ( S \setminus X \right ) \operatorname{and} W \cap Z = L \}\) and \(T_2 = \{ \operatorname{span}\{w\} \oplus \operatorname{span}\{x\} : w \in \left ( W \setminus L \right ) \operatorname{and} x \in \left ( X \setminus L \right ) \}\). By similar reasoning as in previous points, we get that \(\left\vert{T_1}\right\vert = q {n - 2 \brack 1}_{q} - 1\), additionally subtracting one to exclude \(X\) from the count of two-dimensional subspaces of \(V\) that share exactly \(L\) in common with \(W\). There are then \(\left ( \frac{\left\vert W \setminus L \right\vert}{q - 1} \right ) \left ( \frac{\left\vert X \setminus L \right\vert}{q - 1} \right ) = \left ( \frac{q^{2} - q}{q - 1} \right )\left ( \frac{q^{2} - q}{q - 1} \right ) = q^{2}\) ways to select a one-dimensional subspace of \(L_1\) of \(W\) and then select a one-dimensional \(L_2\) of \(X\) in order to construct a two-dimensional subspace \(Y = L_1 \oplus L_2 \in S\) of V such that \(Y \cap L = \{ 0 \}\); this means here that \(\left\vert{T_{2}}\right\vert = q^{2}\). Hence \(\left\vert{T}\right\vert = \left\vert{T_1 \sqcup T_2}\right\vert = \left\vert{T_1}\right\vert + \left\vert{T_2}\right\vert = \left ( q^{2} {n - 2 \brack 1}_{q} - 1 \right ) + q^{2}\). Therefore every pair of adjacent vertices on \(G\) share \(\left ( q^{2} {n - 2 \brack 1}_{q} - 1 \right ) + q^{2}\) neighbours in common, since the choice of edge in this context is arbitrary.
-
Select an arbitrary pair \(W\) and \(X\) of distinct non-adjacent vertices in \(S\). Then there \(\left({2 \brack 1}_q \right)\left({2 \brack 1}_q \right) = \left({2 \brack 1}_q \right)^{2}\) ways to select a one-dimensional subspace \(L_1\) of \(W\) and then select a one-dimensional subspace \(L_2\) of \(X\) in order to construct a two-dimensional subspace \(Y = L_1 \oplus L_2 \in S\) of \(V\) such that \(Y \cap W = L_1\) and \(Y \cap X = L_2\); this means here that \(W\) and \(X\) share \(\left({2 \brack 1}_q \right)^{2}\) neighbours in common. Therefore every pair of distinct non-adjacent vertices on \(G\) share \(\left({2 \brack 1}_q \right)^{2}\) neighbours in common, since \(W\) and \(X\) in this context are arbitrary.
Hence \(G \cong J_q(n,2)\) is an \(\operatorname{SRG}\left ( {n \brack 2}_{q}, q {2 \brack 1}_{q} {n - 2 \brack 1}_{q} , \left ( q {n - 2 \brack 1}_{q} - 1 \right ) + q^{2}, \left ( {2 \brack 1}_{q} \right )^{2} \right)\); the general result then follows, since \(n\) and \(q\) in this context are arbitrary.
Note that \(J_q(n,k) \cong J_q(n, n - k)\), the diameter of \(J_q(n,k)\) is \(\operatorname{min}(k, n - k)\), and \(J_q(n,k)\) is strongly regular if and only if its diameter is 2 for all natural numbers \(n,k\) where \(k \leq n\) and prime powers \(q\). The parameters of any strongly regular Grassmann graph can then be deduced from this, together with the result that I have verified in this post.