# Strongly regular graph over subspaces

Let $\Gamma = (V,E)$ be the graph with $V = \{ U \leq \mathbb{F}_q^4 \, | \, \dim(U) = 2\}$ and $E = \{ \{U_1,U_2\} \, | \, \dim(U_1 \cap U_2) = 1 \}$. Show that $\Gamma$ is a strongly regular graph and caluclate its parameters $(n,k,\lambda,\mu)$.

It is clear that $n = \frac{(q^4-1)(q^4-q)}{(q^2-1)(q^2-q)} = (q^2+1)(q^2+q+1)$. Now I'd like to determine the regularity, let $U_1 = \left<v_1,v_2\right>$, then I need to count the $\left<w_1,w_2\right> = U_2 \leq F_q^4$ with $U_1 \cap U_2$ is a line.

Let $M = (v_1|v_2|w_1|w_2) \in \mathbb{F}_q^{4 \times 4}$ be the matrix with column-vectors from the basis of both subspaces. $U_1 \cap U_2$ has dimension $1$ iff $M$ has rank $3$. Now I'm trying to count the number of possible vectors for $w_1$ and $w_2$.

$w_1$ can not be $0$ or linear dependent to $v_1,v_2$ and therefore there exist $q^4-(q^2-1)$ possibilities. $w_2$ can not be $0$ and linear dependent to $w_1$ but linear dependent to $v_1,v_2$. My assumption for $k$ would be the product of both possibilites. However, I'm struggling to calculate them properly.

Apart from that my question is how to calculate $\lambda$ and $\mu$?

Nice work so far, you have $n$.

To figure out $k$, you take an arbitrary 2-dimensional subspace $U_{1} = \langle v_{1}, v_{2} \rangle$, as you have done; to count the subspaces $U_{2}$, it is easiest to restrict yourself to the case where $w_{1} \in U_{1}$; (Note: it is ok to have $w_{1}$ linearly dependent to $v_{1}$ and $v_{2}$, in fact it is best to assume that this is the case). So count the number of possible choices for $w_{1}$, dividing by $(q-1)$ to account for vectors that determine the same line of $U_{1}$. Then, once you have chosen $w_{1}$, count the number of possibilities for $w_{2} \not \in U_{1}$ (again, dividing afterwards to account for overcounting).

Calculating $\lambda$ and $\mu$ is a bit tougher.

For $\lambda$, try to consider $U_{1} = \langle v,u \rangle$ and $U_{2} = \langle v,w \rangle$, sharing the line $\langle v \rangle$. Now you want to consider the number of subspaces $U_{3}$ sharing a line with both. Consider separately the case where $U_{3}$ contains $\langle v \rangle$, and the case where $U_{3}$ intersects $U_{1}$ and $U_{2}$ in different lines (hint: if you take lines through the origin $\ell_{1} \in U_{1}$ and $\ell_{2} \in U_{2}$ with $\ell_{1} \neq \ell_{2}$, then $\langle \ell_{1}, \ell_{2} \rangle$ uniquely determines $U_{3}$).

• Note that if you have $n$, $k$ and $\lambda$, then counting edges joining vertices adjacent to a vertex $u$ to a vertex at distance two from $u$ gives that $k(k-1-\lambda)=(n-1-k)\mu$. To my mind it is easier to compute $\mu$ than $\lambda$. – Chris Godsil Dec 2 '16 at 0:39
• @ChrisGodsil Very true, that's a good point that to compute $\mu$ you don't have to consider two separate cases for $U_{3}$. – Morgan Rodgers Dec 2 '16 at 2:30
• @MorganRodgers Thank you so far, so let me try to do the calculation. Let $w_1$ be in $U_1$, therefore it is linear dependent to $v_1,v_2$. In $U_1$ there are $q^2$ vectors. Since I don't want $w_1$ to be $0$ there are $\frac{q^2-1}{q-1} = q+1$ possibilities. For $w_2$ it would be $\frac{q^4-q^2}{q-1} = q^2(q+1)$ possibilites. Hence, $k = q^2(q+1)^2$. – PeterMcCoy Dec 3 '16 at 13:07
• @ChrisGodsil I know the relation/equation between the parameters but if I have to show that $\Gamma$ is a strongly regular graph, I have to first prove the existence of all parameters and can then use this equation to prove the "plausibility" or am I wrong? – PeterMcCoy Dec 3 '16 at 13:10
• @PeterMcCoy: you're correct. But you can use symmetry to see that the graph is strongly regular - the linear group maps pairs of subspaces to pairs of subspaces while preserving the dimension of the intersection. – Chris Godsil Dec 3 '16 at 13:24