I recently finished my research visit to UWA where I worked with John Bamberg and Gordon Royle on some finite geometrical problems related to cages. So this seems like the right time for me to write a blog post about these graphs.
A graph is a simple undirected graph which is -regular and has girth , or in other words, every vertex in the graph is adjacent to exactly other vertices and the length of the shortest cycle in the graph is . For example, the following is a graph, which is the well-known Petersen graph.
Say is a graph. Pick a vertex of . Then there are vertices of adjacent to . None of these vertices are adjacent among each other since that would give us a triangle in , which contradicts the fact that the girth of is five. Each of these vertices is adjacent to more vertices besides , all of which must lie at distance from . Moreover, these vertices are distinct since otherwise we will get a cycle of length in . Therefore, we see that has at least vertices. Note that for this number is equal to , and hence the Petersen graph above is the smallest graph.
The argument above generalises to show that for odd , the number of vertices in a graph is at least . When is even we can count the number of vertices at distance at most from a fixed edge, which shows that the number of vertices is at least . These lower bounds on the number of vertices in a graph are collectively known as the Moore bound and the graphs which have these many vertices are known as Moore graphs. The Petersen graph above is an example of a Moore graph. Interestingly, there are very few Moore graphs!
Using spectral methods, it has been shown that the Moore graphs can only exist in the following cases: (a) and (cycles), (b) and (complete graphs), (c) and (complete bipartite graphs), (d) and , (e) and there exists a generalized -gon of order . The Moore graph is the Petersen graph, the Moore graph is the Hoffman-Singleton graph and its a famous open problem in mathematics whether a Moore graph exists or not. Generalized -gons are certain point line geometries that were defined by Tits in his famous paper on trialities, and they are precisely the rank 2 buildings. Their incidence graph is biregular, has diameter , and girth . Those generalized -gons whose incidence graph is regular with degree can only exist for and in each of these cases we only have constructions where is a prime power! We are nowhere near proving that has to be a prime power. For example, whether a projective plane (which equivalent to a generalized -gon) of order exists or not is still a big open problem.
Since there are very special values of and for which a Moore graph exists, it is natural to consider the following problem:
Find the smallest number of vertices in a graph.
The graphs which have exactly vertices are known as cages. It was shown by Erdős and Sachs (see the Appendix in the survey on cages *) that cages exist for every value of and . But besides the Moore graphs, explicit examples of cages, or equivalently the exact value of is only known for a few values of and . See the database of Brouwer for a full list and description of the known cages.
Therefore, a natural problem that mathematicians have worked on is to construct small graphs and thus improve the upper bounds on . The bound that Erdős and Sachs proved is which was improved later by Sauer to for odd and for even. These upper bounds are roughly square of the Moore bound. This square was improved to 3/2 power by Lazebnik, Ustimenko and Woldar who proved that if is the smallest odd prime power bigger than , then where for . Since we can always find an odd prime between and , this bound is roughly of the power of the lower bound.
For specific values of , the known upper bounds are in fact much better than these general bounds. I will talk about how these bounds are obtained for by looking at certain subgraphs of the known Moore graphs in a later post where I will also discuss our new results in this direction.
 Dynamic Cage Survey by Geoffrey Excoo and Robert Jajcay.
 The cage problem by Michael Giudici.
 Balaban 10-cage | Visual Insight by John Baez.
* A simpler proof using Cayley graphs was later given by Biggs. In both of these proofs we need the fact that for all and , we have . The only place where I have found an explicit proof of this is in the paper of Fu, Huang and Rodger.