A generalised quadrangle with lines of size and with points on each line (a , for short) has a lot of “regularity” – and as we learned from a previous post, any finite “non-degenerate” GQ is a for some 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

The

collinearity graphof a GQ is the graph with the vertex set two vertices are adajcent iff they arecollinear, i.e. if there exists such that

For a such a graph is *strongly regular*, see wikipedia for a good short intro.

Basically, a graph is *strongly regular* if it is

- regular, i.e. each vertex is adjacent to other vertices;
- for each edge there are exactly vertices such that
- for each non-edge there are exactly vertices such that

One says that when is as above, one has an One famous example of a srg is the Petersen graph. It is an

Exercise.

- Prove that the collinearity graph of an is an
- Compute as a function of and (namely, it is )

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

Adjacency matrix of a graph is the matrix that has for each and otherwise

In particular and the -th row sum is the number of vertices adjacent to This means that the all-1 vector is an eigenvector of with eigenvalue 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 an the adjacency matrix has at most 3 distinct eigenvalues, namely and

This follows from the fact that multiplication of 0-1 matrices boils down to computing certain combinatorial parameters of underlying graphs. E.g. is the number of length 2 walks from to In our case we have

where is the identity matrix and the all-1 matrix. Any eigenvector with eigenvalue must be orthogonal to the -eigenvector, in particular Thus

and this translates into

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

Moreover, one can compute the multiplicities of the eigenvalues of

Indeed, we know that has multiplicity and so the other two eigenvalues have multiplicities and that satisfy

- (by just discussed) and
- (as the trace of is 0.)

We can solve these two linear equations to obtain

These are powerful conditions that rule out large sets of tuples as must be nonnegative integers!

For an srg arising from a one can compute that the eigenvalues of are and

This gives one, by computing the multiplicities, that for one has With more work (one needs e.g. the *Krein bound*) the case can be ruled out.

Tags: algebra, combinatorics, MAS932, maths

## Leave a Reply