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?

Blog at WordPress.com.

Up ↑