21
$\begingroup$

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#)

$\endgroup$
  • 1
    $\begingroup$ Small curiosity: Is there a reason you use max-degree? Since the graph is regular, degree should be pretty clear, shouldn't it? For the same reason, shouldn't the condition for $|E|$ be an equality? $\endgroup$ – chazisop Jun 25 '15 at 20:25
  • $\begingroup$ Oh, right. I guess it's a remnant of mine from also at the same time looking into the degree-diameter problem. I'll edit. $\endgroup$ – Konstantinos Koiliaris Jun 25 '15 at 20:38
  • 2
    $\begingroup$ Could you give citations to some of these facts about the 57-Moore graph? The list of facts seems like it could be a great mini-survey. $\endgroup$ – Joshua Grochow Jun 26 '15 at 4:31
  • 1
    $\begingroup$ I put up most of the references. I seem to not be able to find the independence number one. If someones recalls where it is from, let me know. $\endgroup$ – Konstantinos Koiliaris Jun 26 '15 at 16:06
  • 3
    $\begingroup$ @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. $\endgroup$ – Konstantinos Koiliaris Jun 26 '15 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.