For fixed integers , and odd , a Moore graph is an -regular graph of girth which has the minimum number of vertices among all such graphs with the same regularity and girth.
(Recall, A the girth of a graph is the length of its shortest cycle, and it’s regular if all its vertices have the same degree)
Problem (Hoffman-Singleton): Find a useful constraint on the relationship between and for Moore graphs of girth and degree .
Note: Excluding trivial Moore graphs with girth and degree , there are only two known Moore graphs: (a) the Petersen graph and (b) this crazy graph:
The solution to the problem shows that there are only a few cases left to check.
Solution: It is easy to show that the minimum number of vertices of a Moore graph of girth and degree is . Just consider the tree:
Provided , we will prove that must be either or . The technique will be to analyze the eigenvalues of a special matrix derived from the Moore graph.
Let be the adjacency matrix of the supposed Moore graph with these properties. Let . Using the girth and regularity we know:
- since each vertex has degree .
- if is an edge of , since any walk of length 2 from to would be able to use such an edge and create a cycle of length 3 which is less than the girth.
- if is not an edge, because (using the tree idea above), every two vertices non-adjacent vertices have a unique neighbor in common.
Let be the matrix of all 1’s and the identity matrix. Then
We use this matrix equation to generate two equations whose solutions will restrict . Since is a real symmetric matrix is has an orthonormal basis of eigenvectors with eigenvalues . Moreover, by regularity we know one of these vectors is the all 1’s vector, with eigenvalue . Call this . By orthogonality of with the other , we know that . We also know that, since is an adjacency matrix with zeros on the diagonal, the trace of is .
Multiply the matrices in the equation above by any , to get
Rearranging and factoring out gives . Let , then the non- eigenvalues must be one of the two roots: or .
Say that occurs times and occurs times, then . So we have the following equations.
From this equation you can easily derive that is an integer, and as a consequence for some integer . With a tiny bit of extra algebra, this gives
Implying that divides , meaning , and as a consequence .
Discussion: This is a strikingly clever use of spectral graph theory to answer a question about combinatorics. Spectral graph theory is precisely that, the study of what linear algebra can tell us about graphs. For an deeper dive into spectral graph theory, see the guest post I wrote on With High Probability.
If you allow for even girth, there are a few extra (infinite families of) Moore graphs, see Wikipedia for a list.
With additional techniques, one can also disprove the existence of any Moore graphs that are not among the known ones, with the exception of a possible Moore graph of girth and degree on vertices. It is unknown whether such a graph exists, but if it does, it is known that
You should go out and find it or prove it doesn’t exist.
Hungry for more applications of linear algebra to combinatorics and computer science? The book Thirty-Three Miniatures is a fantastically entertaining book of linear algebra gems (it’s where I found the proof in this post). The exposition is lucid, and the chapters are short enough to read on my daily train commute.