Dan Cranston

The Search for Moore Graphs: Beauty is a Rare Thing

Abstract: A Moore Graph is k-regular, has diameter 2, and has k2+1 vertices- that's the most vertices you could hope for in such a graph. These graphs are vertex-transitive and evoke a wonderful sense that "everything fits just right." It's not hard to find Moore graphs when k is 2 or 3; they're the 5-cycle and the Petersen graph. But for larger k, they're very rare. In 1960, Hoffman and Singleton gave a beautiful proof that Moore Graphs can only exist when k is 2, 3, 7, or 57. For k equal to 2, 3, or 7, they showed that there exists a unique Moore Graph. When k is 57, nobody knows. I'll present Hoffman and Singleton's proof and take a wild stab at what they might have been thinking when they discovered it.