Title: The Quest for the Mythical 57-regular Moore Graph:
Removing Certain Classes of 4-cycles from a Partial Solution
Abstract: Since 1968 an ongoing quest to find the hypothesized 57-regular
Moore graph has been going on. Arguably the hardest existential question
in graph theory, this problem has defeated both the increases in computing
power and developments in graph theory since then. The problem statement
is very simple: find an undirected regular graph of degree 57 having
diameter 2 and girth 5. Diameter refers to the maximal distance between
vertices, and girth refers to the smallest cycle length. If this graph
exists, several of its properties are known and I will explain their
derivation in the first part of this talk. For instance, the number of
vertices must be 3250 and the number of edges 92625. The graph cannot be
vertex-transitive and the order of its automorphism group is at most 375.
As the layout of 3249 edges is already known, the second part of the talk
will focus on the precise configuration of the remaining 89376 edges. I
will explain how to remove all 3-cycles from a partial solution and how
to classify all remaining 4-cycles in three categories A, B, C. I wrote a
computer program that was able to remove both the 3-cycles and the 4-cycles
of type A and B using a discrete optimization method. How to remove the
C-class of 4-cycles is unknown at this point in time. Those who attend this
talk can perhaps help by sharing their ideas about this problem or by
relating the algorithm I will present to their own work in the field of
discrete optimization.