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 and diameter . Equivalently, a Moore graph is just a regular graph with girth equal to . 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 and . 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?