Some people make a habit of occasionally visiting Wikipedia’s front page and following hyperlinked phrases down a rabbit hole of articles. I do a similarly thing with Andries Brouwer’s tables of strongly regular graphs, which leads to a cascade of papers, checking BCN and computing stuff in Sage.  How does that happen exactly? As usual in math, we now need to start with some definitions.

Definitions

A strongly regular graph is a \(k\)-regular graph where every pair of adjacent vertices has \(a\) common neighbours and every pair of non-adjacent vertices has \(c\) common neighbours. The tuple \((n,k,a,c)\) is called the parameter set of the strongly regular graph (or SRG). For example, the Petersen graph is a SRG with parameter set \((10,3,0,1)\). We immediately, see that these number \(n,k,a\) and \(c\) have to satisfy some conditions, some trivial (\(n>k\) and \(a,c \leq k\) and others less so.

Brouwer’s tables consists of all possible parameter sets for \(n\) up to \(1300\) which have passed some elementary checks. The parameters which are in green are classes where it has been confirmed that there does in fact exist at least one SRG with those parameters. The ones in red have been shown by other means (failing to satisfy the absolute or relative bound, for example) to not be parameter sets of any SRGs. The entries in yellow are parameter sets where the existence of a SRG is still open. This leads us to …

Non-existence of SRGs

Finding whether or not a putative SRG exists is a pretty interesting problem; the existence of the \(57\)-regular Moore graph which is a SRG with parameters \((3250, 57,0,1)\) is a long-standing open problem in algebraic graph theory. Today, we’ll look at the parameter set \((49,16,3,6)\), which holds the distinction of being the first red entry in Brouwer’s tables which is not a conference graph and also not ruled out by the absolute bound. This means that it was ruled out by a somewhat ad-hoc method; in this case, it was ruled out by Bussemaker, Haemers, Mathon and Wilbrink in this 1989 paper. However, computers have come along way since 1989, so instead of following their proof, I will give another proof, which uses computation (which was done in Sage).

That’s way too many 2’s, this SRG can’t exist

Suppose \(X\) is a SRG with parameter set \((49,16,3,6)\). This graph has eigenvalues $$16, 2^{(32)}, \text{ and } -5^{(16)}$$ where the multiplicities are given as superscripts. We’ll proceed by trying to build \(X\). First, we “hang a graph by a vertex” as follows:

The main thing to note right away is that neighhourhood of a vertex \(x\) in \(X\), denoted \(\Gamma_1(x)\) in the diagram, is a \(3\)-regular graph on \(16\) vertices. This is excellent news because there are only 4060 such graphs and one can generate them using geng, or download them from Gordon Royle’s website.

Next, we apply interlacing. We denote by \(\lambda_i(G)\) the \(i\)th largest eigenvalue of \(G\). Since \(\Gamma_1(x)\) is an induced subgraph of \(X\), interlacing theorem tell us $$ \lambda_i(X) \geq \lambda_i(\Gamma_1(x)) \geq \lambda_{33 + i}(X)$$ for \(i=1,\ldots,16\). In particular, we see that the second largest eigenvalue of \(\Gamma_1(x)\) is at most  \(2\). In general, this gives us all kinds of useful information (for example, that \(\Gamma_1(x)\) has to be connected), but since we only care about cubic graphs on \(6\) vertices, we can just go ahead and check which of them have this property. In turns out that only 35 cubic graphs on 16 vertices have this property.

If I have an induced subgraph \(Y\) of \(X\) on 18 vertices, the  interlacing theorem would give the following:  $$ \lambda_2(X) \geq \lambda_2(\Gamma_1(x)) \geq \lambda_{33}(X).$$ Recalling that the second and 33rd largest eigenvalues of \(X\) are both \(2\), we see that any subgraph of \(X\) on 18 vertices must have its second eigenvalue equal to \(2\). Since \(\lambda_i(G)\) already has 16 vertices, we’re not far off. Let \(y\) be a vertex in the second neighbourhood of \(x\) and we will consider the subgraph \(Y\) induced by \(x\), the neighbours of \(x\) and \(y\).

In terms of the computation, we try to add \(x\) and \(y\) to each of the remaining 35 cubic graphs. We can always choose \(y\) to be adjacent to a fixed vertex in \(\Gamma_1(x)\) and so there are \({16 \choose 5}\) ways of adding the other \(5\) edges incident to \(y\). Thus we have 35(3003) candidates for \(Y\). A quick computation later, we see that none of those graphs have \(2\) as the second largest eigenvalue, which contradicts the existence of \(X\).

So what? And also, now what?

It’s fun proving the non-existence of a SRG that is already known not to exist, but clearly what we actually want to do is convert some yellow entries of Brouwer’s table to either red or green. The method here (as well as that of the original paper of  Bussemaker, Haemers, Mathon and Wilbrink) works because the multiplicity of \(2\) as an eigenvalue is really large. The degree of the graph is equal to the multiplicity of its smallest eigenvalue, which smells of some kind of duality. This happens, for example, in the complement of Clebsch graph (which, by the way, is formally self-dual). The next open case where this occurs is \((100,33,8,12)\).  In this case, the first neighbourhood of a vertex would be a \(8\)-regular graph on 33 vertices, with a fairly large spectral gap. We probably don’t want to be generating all such graphs, so some new idea is needed.