«
»

Strongly regular graphs and generalised quadrangles

By Dima

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.

Tags: , , ,

This entry was posted on 16 March, 2009 at 15:27 and is filed under undergrad maths. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply