## Strongly regular graphs and generalised quadrangles

A generalised quadrangle with lines of size $s+1$ and with $t+1$ points on each line (a $GQ(s,t)$, for short) has a lot of “regularity” – and as we learned from a previous post, any finite “non-degenerate” GQ is a $GQ(s,t)$ for some $s,t\geq 2.$ This regularity allows for the use of quite a bit of linear algebra and algebraic graph theory in investigating them.
One considers the collinearity graph of the GQ $(P,L).$

The collinearity graph of a GQ $(P,L)$ is the graph with the vertex set $P,$ two vertices $u,v$ are adajcent iff they are collinear, i.e. if there exists $\ell\in L$ such that $u,v\in \ell.$

For a $GQ(s,t),$ such a graph is strongly regular, see wikipedia for a good short intro.
Basically, a graph $\Gamma=(V,E)$ is strongly regular if it is

• regular, i.e. each vertex is adjacent to $k$ other vertices;
• for each edge $(u,v)\in E,$ there are exactly $\lambda$ vertices $w\in V$ such that $(u,w),(v,w)\in E;$
• for each non-edge $(u,v)\in \binom{V}{2}-E,$ there are exactly $\mu$ vertices $w\in V$ such that $(u,w),(v,w)\in E.$

One says that when $\Gamma$ is as above, one has an $srg(|V|,k,\lambda,\mu).$ One famous example of a srg is the Petersen graph. It is an $srg(10,3,0,1).$

Exercise.

1. Prove that the collinearity graph of an $GQ(s,t)$ $(P,L)$ is an $srg(|P|,s(t+1),s-1,t+1).$
2. Compute $|P|$ as a function of $s$ and $t.$ (namely, it is $(s+1)(st+1)$)

An important tool in studying srg’s, and graphs in general, is the

Adjacency matrix of a graph $\Gamma=(V,E)$ is the $|V|\times |V|$ matrix $A=A(\Gamma)$ that has $A_{uv}=1$ for each $(u,v)\in E$ and otherwise $A_{uv}=0.$

In particular $A=A^T$ and the $v$-th row sum is the number of vertices adjacent to $v.$ This means that the all-1 vector is an eigenvector of $A$ with eigenvalue $k.$ In fact, this is the largest eigenvalue, and for the connected graphs it has 1-dimensional eigenspace. For srgs, much more can be said.

For a connected $\Gamma$ an $srg(v,k,\lambda,\mu),$ the adjacency matrix $A$ has at most 3 distinct eigenvalues, namely $k$ and $(\lambda-\mu\pm\sqrt{(\lambda-\mu)^2-4(k-\mu)})/2.$

This follows from the fact that multiplication of 0-1 matrices boils down to computing certain combinatorial parameters of underlying graphs. E.g. $(A^2)_{uv}$ is the number of length 2 walks from $u$ to $v.$ In our case we have

$\displaystyle A^2=kI+\lambda A+\mu (J-I-A),$

where $I$ is the identity matrix and $J$ the all-1 matrix. Any eigenvector $z$ with eigenvalue $\theta\neq k$ must be orthogonal to the $k$-eigenvector, in particular $Jz=0.$ Thus

$\displaystyle A^2z=kIz+\lambda Az-\mu (I+A)z,$

and this translates into $\theta^2=k+\lambda\theta-\mu-\mu\theta,$

a quadratic equation! It remains to compute its solutions to establish the claim.

Moreover, one can compute the multiplicities of the eigenvalues of $A.$
Indeed, we know that $k$ has multiplicity $1,$ and so the other two eigenvalues have multiplicities $m_1$ and $m_2$ that satisfy

• $m_1+m_2=v-1$ (by just discussed) and
• $m_1\theta_1+m_2\theta_2+k=0$ (as the trace of $A$ is 0.)

We can solve these two linear equations to obtain

$m_{1,2}=\left(v-1\pm\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2-4(k-\mu)}}\right)/2.$

These are powerful conditions that rule out large sets of tuples $(v,k,\lambda,\mu),$ as $m_1,m_2$ must be nonnegative integers!

For an srg arising from a $GQ(s,t),$ one can compute that the eigenvalues of $A$ are $s(t+1),$ $s-1,$ and $-t-1.$

This gives one, by computing the multiplicities, that for $s=2$ one has $t\in\{1,2,4,10\}.$ With more work (one needs e.g. the Krein bound) the case $t=10$ can be ruled out.