I want more Moore graphs…

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. 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. This is super cool! You, Dr. Royle wrote the textbook I’m currently using in my Graph Theory class! I was just stumbling through some homework problems related to this infamous Moore graph, and here you are! Thank you, sir!

  2. The Hoffman-Singleton graph is built from copies of the Petersen graph. Must a Moore graph on 3250 vertices
    contain a copy of the Petersen graph?

  3. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: