You may have heard about the open problem on Moore graphs which is one of the most famous problems in Algebraic Graph Theory. Here is a brief synopsis…

A Moore graph is a regular graph which is extremal in the sense that its number of vertices is large compared to its degree $k$ and diameter $d$. Equivalently, a Moore graph is just a regular graph with girth equal to $2d+1$. There is much one can say about Moore graphs, but I just want to concentrate on the diameter 2 case; these are exactly the strongly regular graphs with $\lambda=0$ and $\mu=1$. A nice algebraic graph theory argument leads to the Hoffman-Singleton Theorem:

Theorem: Any Moore graph with diameter 2 must have degree 2, 3, 7, or 57.

The graphs with degree 2, 3, and 7 are the pentagon, Petersen graph, and Hoffman–Singleton graph, respectively, and these are the unique such diameter 2 graphs with these degrees. The last case, degree 57, is unsolved; we still do not yet know whether such a graph exists!

What we do know is that a Moore graph of diameter 2 and degree 57 is vertex-intransitive and the automorphism group has order not divisible by 4. In fact, an involutary automorphism must fix 56 points. Not much more could be said until very recently, and I want to make special mention of a recent preprint of Martin Mačaj and Jozef Širáň. They prove that the automorphism group must have size at most 375.

So what do you think? Does a Moore graph of diameter 2 and degree 57 exist?

## 7 thoughts on “I want more Moore graphs…”

1. Gordon Royle says:

Here’s some blue-sky numerology (I think Chris Godsil told me this originally, but I can’t remember).

Spectral theory tells us that an independent set in this hypothetical Moore graph can have at most 400 vertices, leaving 2850 left over.

These are magic numbers though, because 400 is the number of points in PG(3,7) and 2850 is the number of lines in PG(3,7). So perhaps we can construct a Moore graph with an independent set of size 400 by using the points of PG(3,7) as the independent set and the lines of PG(3,7) as the remaining vertices. The natural incidence between points and lines in PG(3,7) yields exactly the required number of edges between the two parts.

So this leaves us just the challenge of deciding adjacency among the 2850 “line-type” vertices.

If we take one of the 400 “point-type” vertices, then it has 57 line-type vertices as neighbours, and each of those has a further 49 line-type vertices as its neighbours. All 57.50 = 2850 of these must be distinct and so this configuration is a collection of 57 spreads of PG(3,7) that collectively use all the lines, or in other words a packing of PG(3,7).

So all we need to do is find 400 packings of PG(3,7) that fit together properly!!

1. Evgeny Abrahin says:

Co-o-o-l… I’ll try to find these packings inside the Leach lattice.

4. Further to Gordon’s post, here is some evidence that a nice collection of spreads of PG(3,7) might give us a new Moore graph. Consider PG(3,q) in general, and suppose we have a packing of PG(3,q), that is, $q^2+q+1$ disjoint sets of $q^2+1$ lines which each form a partition of the points. So for example, there are precisely two isomorphism classes of packings of PG(3,2), each giving us 7 spreads comprising the packing. But there is something else: I’ll call it a 5-fold packing. It is a set of 35 spreads such that every line lies in five spreads. There is a subgroup of PGL(4,2) isomorphic to $A_7$, and it has an orbit of size 35 on regular spreads. Fix this 5-fold packing of PG(3,2) and let $\Gamma$ be the graph with vertices the points and lines of PG(3,2) and an adjacency relation defined by the following criteria: (i) no two points are adjacent, (ii) a point and line are adjacent if they are incident, and (iii) two distinct lines are adjacent if they are contained in 2 common spreads of the 5-fold packing. Remarkably, we get the Hoffman-Singleton graph.