<p>I am looking into the last open question regarding the existence of <a href="https://en.wikipedia.org/wiki/Moore_graph" rel="noreferrer">Moore Graphs</a> of diameter 2. A problem that has been open in combinatorics for more than 55 years.</p>

<p>You may recall that <a href="http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5392463" rel="noreferrer">Hoffman and Singleton</a> proved that the only <em>Moore Graphs</em> [: 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 <strong>57</strong>, but for no other degrees.</p>

<p>Little is really known about the <em>57-Moore Graph</em>. 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.</p>

<p><strong>The 57-Moore Graph</strong> will have:</p>

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

<p>Some more results from combinations of the above:</p>

<ul>
<li><strong>Proposition 1. [MS10]</strong> <em>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.</em></li>
</ul>

<p>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? </p>

<p>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?</p>

<p>Thank you.</p>

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

<p>[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 (<a href="http://www.sciencedirect.com/science/article/pii/S0024379509003735#" rel="noreferrer">http://www.sciencedirect.com/science/article/pii/S0024379509003735#</a>)</p>

CC BY-SA 3.0
2015-06-26T16:37:20.953Z
@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 (http://www.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.
Konstantinos Koiliaris
CC BY-SA 4.0
2021-06-15T13:38:29.697Z
Survey [2019]: https://www.sciencedirect.com/science/article/abs/pii/S0024379519300138
Possible does not exist proof [2020]: https://www.youtube.com/watch?v=Q2Uq28TRy0Y
Braully Rocha
CC BY-SA 4.0
2021-11-14T22:55:01.160Z
A purported proof that the graph does not exist. In Russian. October 2020. https://arxiv.org/abs/2010.13443
Mike Atkinson
<graph-theory><open-problem><combinatorics>
$\Delta = 57, d=2$ Moore Graph
Konstantinos Koiliaris
# $\Delta = 57, d=2$ Moore Graph

(Asked by: username_0 on 2015-06-25)

I am looking into the last open question regarding the existence of [Moore Graphs](https://en.wikipedia.org/wiki/Moore_graph) of diameter 2. A problem that has been open in combinatorics for more than 55 years.

You may recall that [Hoffman and Singleton](http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5392463) 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#>)

**Tags:** graph-theory, open-problem, combinatorics
> **Comments:**
> **username_0**: @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 (http://www.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.  
> **username_1**: Survey [2019]: https://www.sciencedirect.com/science/article/abs/pii/S0024379519300138 Possible does not exist proof [2020]: https://www.youtube.com/watch?v=Q2Uq28TRy0Y  
> **username_2**: A purported proof that the graph does not exist. In Russian. October 2020. https://arxiv.org/abs/2010.13443  

---

## 0 answers

