July 8th, 2020

Conway’s 99-graph (and related problems)

https://maths.straylight.co.uk/archives/1299

http://maths.straylight.co.uk/?p=1299

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):</p>

    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.

Constraints on Conway’s 99-graph (and its subgraphs)

https://maths.straylight.co.uk/archives/1315

http://maths.straylight.co.uk/?p=1315

In the previous post, we introduced strongly regular graphs, with a particular interest in whether an srg(99,14,1,2) could exist. In this post, we’ll look at some properties such a graph G – or various subgraphs G’ – would have to satisfy.

(throughout, we’ll use G to refer to any Conway 99-graph, and use ‘subgraph’ to describe graphs obtained by vertex deletions only – sometimes called proper or induced subgraphs – rather than the more general concept which allows edge deletions too.)

The degree of every vertex is necessarily 14

First, then, we should make good on the promise to prove that the degree parameter k is 14, since Conway’s formulation of the problem only specifies the number of vertices and the mutual neighbour parameters λ=1, μ=2.

For this, we’ll use a double counting argument – expressing the same number in two different ways, and equating those expressions. For this, pick any vertex of G and call it vertex 0. Then as G is assumed to be regular, 0 has k neighbours, wlog vertices 1…k. Let A be the set of vertices 1…k, and B be the set of vertices k+1…98 (i.e. all the vertices apart from 0 and its neighbours). The quantity we will count is the number of edges between vertices in A and vertices in B.

  • First, consider any vertex i in A. As a neighbour of vertex 0, they must have precisely one neighbour in common; since all the neighbours of 0 are in A, so there must be an edge from i to precisely one other i’ in A. Apart from the edge linking i to 0, all other edges starting at A must be to vertices in B. For vertex i to have degree k, there must therefore be k-2 edges from vertex i to B. Our choice of vertex i was arbitrary from A, which contains k vertices; so in total there are k(k-2) edges from A to B.
  • Conversely, consider any vertex j in B. j is not a neighbour of vertex 0, so they must have 2 mutual neighbours; necessarily those are vertices of A (else they don’t neighbour 0 either). Thus each of our 98-k vertices k+1…98 contributes 2 edges from B to A, for a total of 2(99-k-1) = 196 – 2k.
  • Since the edges from A to B are precisely the edges from B to A, we have equality: k(k-2) = 196 – 2k. So k^2 = 196, which for positive k forces k=14 as claimed.

The neighbourhood of each vertex is a seven-bladed fan

Implicit in the above was a description of the neighbourhood of any vertex v of G – that is, the subgraph N(v) consisting of that vertex and all of its neighbours. Let 0 be an arbitrary vertex and pick any neighbouring vertex, calling that vertex 1. Then as 0 and 1 are neighbours, they have precisely one mutual neighbour; wlog vertex 2. This gives us a ‘fanblade’ consisting of vertices 0,1,2: neither vertex 1 nor 2 can have any other neighbours in N(0). We can repeat this process to introduce the vertices in pairs 3-4, 5-6, 7-8, 9-10, 11-12 and 13-14. Thus N(0) is a seven-bladed fan:

An arbitrary vertex 0 has 14 neighbours, which can be arranged in pairs a,a+1 such that the only edges are: 0,a; 0,a+1; a,a+1 for odd a.

Up to labelling, N(v) for any v in G is of this form.

Eigenvalue constraints

We will not prove these results here, but any strongly regular graph has precisely 3 eigenvalues whose values and multiplicities are determined by v,k,λ,μ. For our parameters, the eigenvalues of G are therefore:

  • 14, with multiplicity 1
  • 3, with multiplicity 54
  • -4, with multiplicity 44

The interlacing theorem therefore gives strong requirements on the eigenvalues of sufficiently large subgraphs G’ of G. Recall that if A is an n-vertex graph with eigenvalues a_1…a_n and B is obtained from A by deleting a vertex, then the eigenvalues b_1…b_(n-1) of B interlace with the eigenvalues of A:

a_1 ≤ b_1 ≤ a_2 ≤ … ≤ a_(n-1) ≤ b_(n-1) ≤ a_n

For G we have a_1 = a_2 = …. = a_44 = -4, a_45 = a_46 = … = a_98 = 3, a_99 = 14. So if G’ is a 98 vertex subgraph of G, almost all of its eigenvalues are known too: b_1 through b_43 must be -4, and b_45 through b_97 must be 3. The only freedom is in b_44, which can take values in [-4,3]; and b_98, which can take values in [3,14].

Iterating this process, we arrive at the following corollaries:

Let G’ be any subgraph of G. Then:

  • e≥ -4 for any eigenvalue e of G’
  • e≤ 14 for any eigenvalue e of G’
  • If e>3 is an eigenvalue of G’, then e has multiplicity 1
  • There cannot be two eigenvalues e,e’ of G’ such that e’ > e > 3.

Let G’ be a subgraph of G with n vertices. Then:

  • If n ≥ 56, then n-55 of the eigenvalues of G’ must take the value -4
  • If n ≥ 46, then n-45 of the eigenvalues of G’ must take the value 3

Subgraph compatibility with strong regularity

Let a,b be vertices of a subgraph G of G’. If a and b are neighbours in G’, then they are neighbours in G, so there must exist precisely one c in G adjacent to both a and b. If a and b are not neighbours in G’, then they are not neighbours in G either (by our notion of subgraph); so there must exist precisely two vertices d,e in G adjacent to both a and b. However, these vertices c,d,e need not feature in G’ – their absence is not reason to discard G’ as a potential subgraph of G.

Conversely, if a proposed G’ has too many mutual neighbours, then this can never be ‘fixed’ by adding more vertices, so we can rule out such a subgraph. Thus we have:

Let G’ be a subgraph of G. Then:

  • If a and b are adjacent vertices in G’, then they have at most one mutual neighbour in G’
  • If a and b are non-adjacent vertices of G’, then they have at most two mutual neighbours in G’

However, these mutual neighbours must eventually be introduced, and so we can additionally rule out candidate subgraphs where we have missed this opportunity:

Let G’ be a subgraph of G containing a vertex a and all of its neighbours in G, a_1…a_14. Then:

  • Each a_i must neighbour precisely one other a_j
  • For any b in G’ not amongst the a_i (or a itself), b must be a neighbour of precisely two of the a_i

Finally, we have the trivial observation that the regularity condition also restricts G’:

Let a be a vertex of a subgraph G’ of G. Then a has degree at most 14.

~

In the next post we’ll attempt to ‘grow’ our way towards G from a subgraph – we won’t get far enough to make use of our eigenvalue constraints, but we are able to enumerate the possibilities for the subgraph consisting of two adjacent vertices and their combined neighbourhoods. Before that, though, I wanted to note in passing some other properties of the Conway graph that I found during my research, although I don’t know how I would test for them…

Group-theoretic restrictions

  • From “On the (99,14,1,2) strongly regular graph” (pp. 342-355 of this collection), if G exists, it does not have an automorphism of order 11, which implies that the automorphism group cannot be transitive.
  • Example 3.2 of this paper gives the critical group of G.

The neighbourhood of two adjacent vertices in a Conway 99-graph

https://maths.straylight.co.uk/archives/1330

https://maths.straylight.co.uk/?p=1330

In the previous post, we saw that if a is a vertex of a Conway 99-graph G, then up to labelling the only possibility for the neighbourhood of v is the following:

An arbitrary vertex 0 has 14 neighbours, which can be arranged in pairs a,a+1 such that the only edges are: 0,a; 0,a+1; a,a+1 for odd a.

In this post, we describe the results of a search for all possible subgraphs consisting of two adjacent vertices a,b and all of their neighbours in G.

The route

Suppose there exists a Conway-99 graph G, that is, an SRG(99,14,1,2). Let a and b be vertices of G such that a and b are neighbours. Then:

  • a has 14 neighbours, one of which is b
  • b has 14 neighbours, one of which is a
  • By λ = 1, precisely one of these neighbours is a mutual neighbour of both a and b

Thus the graph G’ on a,b and their neighbours consists of 27 vertices (a, b, their mutual neighbour, 12 neighbours of a but not b, and 12 neighbours of b but not a). For convenience, we fix a numbering:

  • a is vertex 0
  • b is vertex 1
  • Their mutual neighbour is vertex 2
  • The remaining neighbours of vertex a are vertices 3 through 14
  • The remaining neighbours of vertex b are vertices 15 through 26

Moreover, we introduce these vertices sequentially using the ‘fanblade’ structures centred at vertices 0 and 1:

  • For i,j in 1…14 we have i,j adjacent iff j = i + 1 and i is odd (as in the diagram above)
  • For i,j in 15…26 we have i,j adjacent iff j = i + 1 and i is odd
  • (The seventh blade for vertex 1 consists of vertices 0 and 2)

Finally, we note that each of the vertices i = 15…26 is not adjacent to vertex 0, thus (by μ = 2) there must be two mutual neighbours of 0,i in G. But as all neighbours of 0 are in G’, namely vertices 1…14, we know that each vertex i = 15…26 is adjacent to precisely 2 of the vertices 1…14.

  • By assumption, vertex 1 is adjacent to vertex i
  • Hence vertex 2 is not adjacent to vertex i (else 0 and i and are mutual neighbours of adjacent vertices 1 and 2, which violates λ = 1)
  • So for each i = 15…26 there is a unique j in 3…14 such that i and j are neighbours.
  • For the first such i=15, all choices of j give equivalent graphs on vertices 0…15. Wlog, we set j=3.
  • Our task then essentially reduces to determining j for each i=16…26, whilst satisfying all our other conditions.

The code

I have produced an assortment of python functions for working efficiently with strongly regular graphs, defaulting to the Conway 99-graph but (hopefully) valid for generic parameters; a public github repository is here. Included is a notebook working through this search; you can view it here if you just want the results without having to run the code yourself.

The rest of this section sketches out some of the challenges in working with srgs, particularly with regard to growing valid supergraphs from a given starting set.

‘Growing’ subgraphs

Adding vertices

As discussed in the previous post, we could in principle work our way from any subgraph G’ to G by considering all possible ways to add a vertex v’ to G’, and discarding those which can be identified as breaching a known subgraph property.

In practice we can terminate even sooner. Consider our starting subgraph N(0) on vertices 0…15. We know that vertex 0 is ‘saturated’ in that all of its neighbours are already present. So any proposed addition of vertex 16 which sets the edge (0,16) is doomed to failure; we should recognise this once rather than try all of the 32,768 possible combinations of (1,16), (2,16), (3,16) …, (15,16).

Matrix representation

Thus far we’ve described everything purely in graph-theoretic terms. However, graphs can be awkward to work with as a data structure; under the hood, we will instead use two dimensional arrays for the corresponding adjacency matrix of a graph.

Usually, this is a matrix of 0s and 1s where the (i,j)th entry is 1 if and only if vertices i and j are adjacent. (Thus when we say the adjacency matrix, we actually mean an adjacency matrix – for an unlabelled graph each choice of vertex numbering will give different – but equivalent – representatives. For this search, however, we have already prescribed a particular labelling.)

However, in the code we’ll extend this to a template form which also allows (i,j) to take the value 2, to indicate an unspecified edge and thus a collection of graphs sharing some common edges and non-edges.

A round of growing

Thus, given a set S of potential n-vertex subgraphs of G, we can grow to the set of potential (n+1)-vertex subgraphs as follows.

For each g in S:

  • Form an (n+1) by (n+1) all-twos matrix a’.
  • Set values a[0,0] through a[n-1,n-1] using the adjacency structure on vertices 0…n-1 given by g.
  • Set the diagonal entry a'[n,n] = 0 (as the new vertex n cannot be a neighbour of itself).
  • For any required edge between vertex n and some vertex i of g, set a'[i,n] and a'[n,i] = 1.
  • For any required non-edge between vertex n and some vertex i of g, set a'[i,n] and a'[n,i] = 0.
  • Add a’ to the template list.

Then, whilst the template list is not empty:

  • Remove any a’ from the template list.
  • Identify the lowest indices i,j such that a'[i,j]=2.
  • Construct new arrays a0 and a1, by first copying a’ but then setting a0[i,j]=a0[j,i]=0 and a1[i,j]=a1[j,i]=1
  • If a0 is a purely 0,1 array then check whether the corresponding graph violates any of the subgraph properties described in the previous post. If not, add it to the solution list.
  • Otherwise, a0 is a template. However, we may already be able to rule it out, if the edges and non-edges specified thus far already specify an invalid feature (for example a vertex of degree 15, or a second mutual neighbour of vertices known to be adjacent). If no such features exist, add a0 to the template list.
  • Perform the previous two steps for a1 in the same way (if an adjacency matrix, add to solution list if valid; if a template, add to template list if not already invalid).

This process necessarily terminates. If the solution list is empty, we have proven that G cannot have any g from S as a subgraph. Conversely, if the solution list S’ is non-empty, we can treat this as a new S and repeat the procedure.

If we knew that at least one of the g in S was a necessary subgraph of G, then if S’ is empty we know that G does not exist. If S’ is nonempty, we now know that at least one of the g’ in S’ is a necessary subgraph of G. Unfortunately, there may be a huge number of these!

Reducing subgraphs

Fortunately, many of them will turn out to be equivalent, as we can take alternative routes to the same (abstract) graph. For example, we argued at the start that attaching vertex 15 to any of j = 3 through 14 was equivalent, so we might as well specify that j it be vertex 3. If we hadn’t done that, we would have obtained 12 valid solutions, one for each choice of j. Having done so, our specification of vertex 16 as the mutual neighbour of vertices 1 and 15 yields 11 solutions, but these only fall into two equivalence classes.

Thus we need to be able to reduce the solution list modulo isomorphism. For the mathematical part I rely upon Nauty, via the orthogonal array package; this documentation (implicitly) describes how to compare a single pair of matrices for equivalence by comparing if they have the same normal form.

It’s easy enough to wrap this comparison up in a function on a pair of arrays. Then the solution list can be reduced by building up a representative list, adding each entry of the solution list only if it is inequivalent to all representatives added so far.

However, this soon turns out to be prohibitively expensive to compute (even with early abort when a match is found), due to the need to put both the representative and the candidate in normal form each time. It is better, therefore, to keep the normal forms along with the representatives, then normalise each candidate once and test for equality to any of the representative normal forms. Since we’re now testing equality, we can go faster by handling this as a dictionary lookup rather than sequentially working through a list… except numpy arrays are mutable and thus can’t be used as keys. Thus I took the questionable choice of converting the normalised array to a full tuple of its entries to get something hashable, likely losing all sorts of representational efficiency: a classic time/memory trade-off that has made the reduction pass negligble compared to the proceeding growing step, but will eventually cause problems!

Validity Testing

One final area where refinement proved necessary was in checking adjacency matrices or templates for invalid features. Given the size of the graphs I was able to work with, the eigenvalue constraints never came into play, so all that is implemented in the code is checks for vertices with excessive degree, adjacent vertices with more than one mutual neighbour, or non-adjacent vertices with more than two mutual neighbours.

As with equivalence testing, it’s pretty easy to write functions that compute the numbers of common neighbours, but when comparing in bulk there is simply too much repeated or otherwise unnecessary work: when you add a vertex to a valid graph, there are only a few places where it can become invalid; and as soon as you find one invalid vertex pair there’s no need to continue testing others. Thus in the code you can find _with_subgraph_mutuals versions of various functions, which again trade off some memory to avoid recomputing known (or more easily derived) values.

The Results

With these various improvements, it takes only a few seconds to recover the possible 27-vertex graphs on 0,1 and their neighbours.

There turn out to be only eleven possibilities. The first of these proceeds in the obvious way, matching 16 to 4, 17 to 5 and so on for this pleasing (after some artistic re-arrangement in yEd!) graph:

The others are more complicated; the notebook describes the differences to this baseline. We can also see that there are no edges in common to all 11; that is, our initial choices did not propagate further and we require further assumptions to force a particular subset of the solutions.

Searching further

Unfortunately, things get much worse from here. The github repo contains two ‘full search’ notebooks. The first proceeds as with our route, trying to introduce neighbours of vertex 2; this will climb to nearly 3 million 33-vertex graphs which it is unable to reduce. The second hands control over edge requirements to a ‘greedy’ version of the growing algorithm, which identifies the vertex closest to being saturated and attempts to add neighbours of that (in the hopes of reaching impossible features sooner). Tiebreaking on label, this therefore favours vertex 3 over vertex 2 but grinds to a halt sooner, at 31 vertices.

I also attempted a sampling rather than exhaustive search: this throws away all but a tiny portion of the results each round in the hope of finding a route through by chance. Unsurprisingly, this has not yielded anything, although the vertex counts attained can be decent.

Finally, it’s natural to ask for the graph consisting of two non-neighbours and their respective neighbours. This sounds like a very minor tweak on what we’ve done here: we add vertex 15 a first non-neighbour of 0, then proceed to saturate it instead of vertex 1. But this too falls victim to acombinatorial explosion of possibilities – whilst it has not yet outright crashed, I expect days of cputime to complete it.

So, for now, I offer this up for others to consider. Perhaps these 11 graphs contain enough information for a mathematical argument rather than trying to push on computationally; or perhaps some of the code I’ve written will be helpful. But if not, it was enjoyable playing around with some ‘proper’ maths for a while, and to overcome the series of programming puzzles presented by each of the search, reduction and validity checking bottlenecks.