I have been on furlough for the last six weeks, which has given me the time to engage properly with a research-grade problem I have been thinking about on-and-off for a number of years! Spoiler alert: this series of posts is not building up to the grand reveal of a solution, but instead is intended to summarise what I’ve learnt and perhaps help ease the way of the next person to give it a try.

Earlier this year, COVID-19 claimed one of mathematics’ greats, John Horton Conway. The Guardian’s obituary does a far better job than I could of illustrating his remarkable range of major contributions across the subject, whilst this MathOverflow post collects together a wonderful assortment of lesser results (including, wonderfully, his ‘discovery’ of the filing cabinet).

But a mathematician lives on in their questions as well as their solutions, and in 2014 Conway had curated five particular problems, an answer to any of which would be rewarded with a thousand dollar prize. I first learnt of this list in 2017, when a counterexample was found by James Davis to the fifth entry, the ‘climb to a prime’ conjecture. Davis is rather unfairly described as an ‘amateur’ in what little coverage I could find of this achievement; but at least that gave me hope that I wouldn’t be completely wasting my time in checking the rest of the list!

Sure enough, the second problem caught my eye as something which, in principle, could be tackled in a similar way to the questions I considered back in my academic research days. Conway’s statement is as follows:

Is there a graph with 99 vertices in which every edge (i.e. pair of joined vertices) belongs to a unique triangle and every nonedge (pair of unjoined vertices) to a unique quadrilateral?

It seems that there are other ways to (mis?)interpret this statement, but in more formal terms this is asking

Does there exist a strongly regular graph with 99 vertices and parameters λ=1, μ=2?

So, what does that mean, and what hope might we have of finding such objects?

Strongly Regular Graphs

For integers v,k,λ,μ a graph G is described as being an srg(v,k,λ,μ) if it satisfies all of the following:

• G has v vertices
• G is regular – the degree (number of neighbours) of every vertex is fixed – and moreover that degree is k
• if two vertices are neighbours, they have precisely λ mutual neighbours
• but if they are not neighbours, they instead have precisely μ mutual neighbours

Thus Conway’s problem is asking for an srg(99,k,1,2). As we’ll see in the next post, only carefully chosen combinations of the four parameters have any chance of yielding a solution. In this case setting v=99, λ=1 and μ=2 is already enough to force a single possibility for the degree k; if Conway’s 99-graph exists, it’s an srg(99,14,1,2). However, it need not be unique – there can be non-isomorphic graphs satisfying the same choice of parameters (and so a natural follow-up challenge given one example is a complete enumeration up to isomorphism).

SRGs with λ=1, λ=2

In fact, Conway’s choice of λ=1, μ=2 is already highly restrictive, with only five possibilities.

• Simplest is the (unique) srg(9,4,1,2):

  

  To me, this is the Paley graph of order 9; such graphs capture information about finite fields, with applications to number theory. But in addition, it’s: a conference graph; toroidal; locally linear; and the graph of the triangular duoprism (from 4 dimensional geometry). It also represents the possible moves of a rook on a 3-by-3 chessboard. Quite a lot for 9 vertices and 18 edges!

• The next smallest possibility is the Conway 99-graph.
• From there, we jump to an srg(243,22,1,2). Remarkably, this does exist, and can be constructed by tying together ideas from coding theory, group theory and graph theory. The result is the Berlekamp–van Lint–Seidel graph, which I won’t attempt to draw!
• The other two possibilities remain open problems:

  Does an srg(6273,112,1,2) exist?

  Does an srg(494019,994,1,2) exist?

Small SRGs

Through a variety of smart search techniques (some of which we’ll consider in the next post), it has been possible to test all the potential parameters corresponding to small strongly regular graphs, where small currently means at most 64 vertices; see the collection of Ted Spence. As the Berlekamp–van Lint–Seidel graph shows, there are larger parameter choices for which strongly regular graphs are known to exist. There are also potentially valid parameters for larger graphs whose existence has been ruled out – for instance, there is no srg(96,38,10,18), but that fact does not immediately follow from the parameters.

Andries E. Brouwer maintains a summary of the possibilities and their current status. From there, we note that the following remains open

Does an srg(65,32,15,16) exist?

But a resolution in the negative (or a full description if solutions do exist) would extend the classification to graphs of at most 68 vertices (as we already know of the 66 vertex examples, and that there are no suitable parameters for 67 or 68 vertices).

A hypothetical Moore graph

As these examples show, the difficulty of finding (or proving non-existence of) strongly regular graphs does not correspond neatly to the number of vertices. The smaller the other parameters, the fewer edges that need to be considered and thus the easier it is to identify forbidden subgraph structures. The most extreme case is λ = 0 – which requires the graph to be triangle-free – and μ = 1. A strongly regular graph that satisfies both of these conditions would be a Moore graph; the only barrier to our complete understanding of such graphs is the following question:

Does an srg(3250,57,0,1) exist?

The existence of a Conway 99-graph (or of any of the other srgs I’ve called out above) is precisely my kind of problem: the statement is easy to understand; a (positive) solution would be easy to verify; but it’s not easy to get from statement to solution! As we’ve seen, in some cases clever constructions can be used to directly manufacture strongly regular graphs, and instances of existing families of graphs may turn out to have strong regularity as a feature. In the next post we’ll consider instead how we might ‘grow’ a solution through careful consideration of a series of subgraphs. As well as being used in the large scale searches of Spence et al, this is precisely the technique I used for my work on (non)cyclotomic graphs back in the day, so I was keen to revisit it and see how far I could get in a different context.