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}$).

  • 1
    $\begingroup$ 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$. $\endgroup$ – Chris Godsil Dec 2 '16 at 0:39
  • $\begingroup$ @ChrisGodsil Very true, that's a good point that to compute $\mu$ you don't have to consider two separate cases for $U_{3}$. $\endgroup$ – Morgan Rodgers Dec 2 '16 at 2:30
  • $\begingroup$ @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$. $\endgroup$ – PeterMcCoy Dec 3 '16 at 13:07
  • $\begingroup$ @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? $\endgroup$ – PeterMcCoy Dec 3 '16 at 13:10
  • $\begingroup$ @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. $\endgroup$ – Chris Godsil Dec 3 '16 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.