## The Cage Problem

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 $(k,g)$ graph is a simple undirected graph  which is $k$-regular and has girth $g$, or in other words, every vertex in the graph is adjacent to exactly $k$ other vertices and the length of the shortest cycle in the graph is $g$. For example, the following is a $(3, 5)$ graph, which is the well-known Petersen graph.

Say $G$ is a $(k, 5)$ graph. Pick a vertex $v$ of $G$. Then there are $k$ vertices of $G$ adjacent to $v$. None of these $k$ vertices are adjacent among each other since that would give us a triangle in $G$, which contradicts the fact that the girth of $G$ is five. Each of these $k$ vertices is adjacent to $k -1$ more vertices besides $v$, all of which must lie at distance $2$ from $v$. Moreover, these $k(k-1)$ vertices are distinct since otherwise we will get a cycle of length $4$ in $G$. Therefore, we see that $G$ has at least $1 + k + k(k-1)$ vertices. Note that for $k = 3$ this number is equal to $10$, and hence the Petersen graph above is the smallest $(3,5)$ graph.

The argument above generalises to show that for odd $g$, the number of vertices in a $(k, g)$ graph is at least $1 + k + k(k-1) + \cdots + k(k-1)^{(g-3)/2}$. When $g$ is even we can count the number of vertices at distance at most $(g-2)/2$ from a fixed edge, which shows that the number of vertices is at least $2(1 + (k-1) + \cdots + (k-1)^{(g-2)/2})$. These lower bounds on the number of vertices in a $(k,g)$ graph are collectively known as the Moore bound and the $(k, g)$ graphs which have these many vertices are known as Moore graphsThe 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) $k = 2$ and $g \geq 3$ (cycles), (b) $g = 3$ and $k \geq 2$ (complete graphs), (c) $g = 4$ and $k \geq 2$ (complete bipartite graphs), (d) $g = 5$ and $k \in \{2, 3, 7, 57\}$, (e) $g \in \{6, 8, 12\}$ and there exists a generalized $g$-gon of order $k - 1$. The $(3, 5)$ Moore graph is the Petersen graph, the $(7,5)$ Moore graph is the Hoffman-Singleton graph and its a famous open problem in mathematics whether a $(57, 5)$ Moore graph exists or not. Generalized $n$-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 $n$, and girth $2n$. Those generalized $n$-gons whose incidence graph is regular with degree $k$ can only exist for $n \in \{6, 8, 12\}$ and in each of these cases we only have constructions where $k - 1$ is a prime power! We are nowhere near proving that $k - 1$ has to be a prime power. For example, whether a projective plane (which equivalent to a generalized $3$-gon) of order $12$ exists or not is still a big open problem.

Since there are very special values of $k$ and $g$ for which a $(k,g)$ Moore graph exists, it is natural to consider the following problem:

Find the smallest number of vertices $c(k,g)$ in a $(k,g)$ graph.

The $(k,g)$ graphs which have exactly $c(k, g)$ 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 $k \geq 2$ and $g \geq 3$. But besides the Moore graphs, explicit examples of cages, or equivalently the exact value of $c(k,g)$ is only known for a few values of $k$ and $g$. 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 $(k, g)$ graphs and thus improve the upper bounds on $(k, g)$. The bound that Erdős and Sachs proved is $c(k, g) \leq 4 \sum_{i = 1}^{g - 2} (k -1)^i$ which was improved later by Sauer to $c(k,g) \leq 2(k-2)^{g-2}$ for $g$ odd and $c(k,g) \leq 4(k-1)^{g-3}$ for  $g$ 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 $q$ is the smallest odd prime power bigger than $k$, then $c(k, g) \leq 2kq^{3g/4 - a}$ where $a = 4, 11/4, 7/2, 13/4$ for $g \equiv 0, 1, 2, 3 \pmod{4}$. Since we can always find an odd prime between $k$ and $2k$, this bound is roughly of the power $3/2$ of the lower bound.

For specific values of $g$, the known upper bounds are in fact much better than these general bounds. I will talk about how these bounds are obtained for $g \in \{6, 8, 12\}$ 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.

[1]  Dynamic Cage Survey by Geoffrey Excoo and Robert Jajcay.

[2] The cage problem by Michael Giudici.

[3] 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 $k \geq 3$ and $3 \leq g_1 < g_2$, we have $c(k, g_1) < c(k, g_2)$. The only place where I have found an explicit proof of this is in the paper of Fu, Huang and Rodger.