# $\Delta = 57, d=2$ Moore Graph

I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years.

You may recall that Hoffman and Singleton proved that the only Moore Graphs [: regular graphs achieving the Moore Bound for a given diameter $d$ and a degree $\Delta$] that exist for diameter $d=2$ are for degree $\Delta=2,3,7$ and possibly 57, but for no other degrees.

Little is really known about the 57-Moore Graph. I will attempt to make a complete list of all facts known about it here and hopefully start a conversation or discover more of them that I may have missed.

The 57-Moore Graph will have:

• Diameter $d=2$, [definition]
• Degree $\Delta=57$, [definition]
• Girth $g=5$, [MS10]
• Number of vertices $|V| = 3250$, [definition]
• Number of edges $|E| = 92625$, [definition]
• At most 375 automorphisms, [MS10]
• Independent Number at most 400, and [reference missing, take it with a grain of salt]
• It will be regular, [definition]
• It will not be vertex-transitive. [Ca83]

Some more results from combinations of the above:

• Proposition 1. [MS10] It's Adjacency Matrix $A$ will satisfy $$A^2 +A - 56I = J,$$ where $I$ is the identity matrix and $J$ the all one matrix. Consequently, it's eigenvalues will be 57, 7, and −8, with multiplicities 1, 1729, and 1520, respectively.

This, to the best of my knowledge, is all we know about the existence of this graph. Have I missed something? Is there something more that we can say about this graph?

Moreover, assuming that this graph exists, is there any hope in pruning down the search space enough to at least try to find it with a semi-brute force approach using supercomputers? Clearly, the search space is too large to brute force even if knew the exact edge count. But can we make other observations towards this or do you think that it is hopeless and that the existence (or not) of this graph would have to be proved some other way?

Thank you.

[Ca83] P.J. Cameron, Automorphism groups of graphs, Selected Topics in Graph Theory II (ed. L. W. Beineke and R. J. Wilson), 89-127, Academic Press, London, 1983.

[MS10] M. Mačaj, J. Širáň, Search for properties of the missing Moore graph, Linear Algebra and its Applications, Volume 432, Issue 9, 15 April 2010, Pages 2381-2398, ISSN 0024-3795 (http://www.sciencedirect.com/science/article/pii/S0024379509003735#)

• @JoshuaGrochow Mačaj and Širáň just a few years ago wrote the above article about the current state of the art on the graph. Also, Miller and Širáň updated their excellent survey on Moore graphs (combinatorics.org/ojs/index.php/eljc/article/view/DS14) with a second edition in may of 2013. I am not sure if there is anything new that can be added yet. Jun 26, 2015 at 16:37
• The max independent set S of size 400 is a simple counting argument. With |S| = 400, such a set is barely possible and one has each vertex in V - S adjacent to exactly 8 vertices in S.
– user34608
Jul 1, 2015 at 4:13
• Survey [2019]: sciencedirect.com/science/article/abs/pii/S0024379519300138 Possible does not exist proof [2020]: youtube.com/watch?v=Q2Uq28TRy0Y Jun 15, 2021 at 13:38
• A purported proof that the graph does not exist. In Russian. October 2020. arxiv.org/abs/2010.13443 Nov 14, 2021 at 22:55