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.

10edb-petersen-svg

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.

Further Reading

[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.

Advertisements

About Anurag Bishnoi

Currently a maths PhD student at Ghent University working in the Incidence Geometry research group. I am broadly interested in combinatorics, finite geometry and group theory.
This entry was posted in Combinatorics, Finite Geometry and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s