There is no McLaughlin geometry

Congratulations to Patric Östergård and Leonard Soicher, who have just completed a big computation whose conclusion is “There is no McLaughlin geometry”. The run-time of the computation was about 250 core-years.

So what did they compute, and why does it matter?

The notions of strongly regular graph and partial geometry were introduced by R. C. Bose in 1963, though they had been around in some form much earlier in Bose’s work. A graph is strongly regular, with parameters n, k, λ, μ if it has n vertices, every vertex has k neighbours, and two vertices have λ or μ neighbours according as they are joined to one another or not. This is a class of graphs of great importance. There are a number of conditions satisfied by the parameters. One, known as the “absolute bound”, is difficult to state but is interesting in that only three graphs are known which attain it. These are the 5-cycle, the Schläfli graph associated with the 27 lines in a cubic surface, and the McLaughlin graph whose automorphism group is McLaughlin’s sporadic simple group. McLaughlin’s graph has parameters n = 275, k = 112, λ = 30, μ = 56.

A partial geometry with parameters s, t, α is a geometry of points and lines in which two points lie on at most one line, every line has s+1 points, every point lies on t+1 lines, and a point P not on a line L is collinear with α points of L. The point graph of a partial geometry (whose vertices are the points, two vertices joined if they are collinear) is strongly regular (but I will leave the calculation of its parameters as an exercise). One interesting feature is that the dual of a partial geometry is also a partial geometry, and so also has a strongly regular point graph (the line graph of the original geometry). Partial geometries played an important role in the characterisation of classes of strongly regular graphs, especially those with smallest eigenvalue −2.

The McLaughlin graph is the unique strongly regular graph with its parameters, up to isomorphism. Also, if there were a partial geometry with parameters (4,27,2), its point graph would have the parameters of the McLaughlin graph, and so would be the McLaughlin graph. So a very natural question is: Is there a partial geometry with these parameters? In other terminology, is the McLaughlin graph geometric? (Note that the other non-trivial graph attaining the absolute bound, the Schläfli graph, is geometric.) That is what has just been resolved in the negative. I am not going to describe the methods (their paper is on the arXiv, here. Suffice to say that a line in the geometry would necessarily be a clique (complete subgraph) of size 5 in the graph; it does have cliques of size 5, but too many to form a geometry, so the problem is to see whether a subset of these cliques can be selected so that each edge lies in exactly one.

Patric talked about this computation, among other things, at our meeting on Discrete mathematics and big data. Of course, it happens not infrequently in discrete mathematics that the result of a huge computation is a single bit, as here. In such cases, we might hope that the answer would be “yes”, and the computer would produce an example of a geometry which could be checked. There is no way of checking the answer “no” other than repeating the computation. The same situation arose in the case of the projective plane of order 10.