Cages

The cages are a class of graphs that I think deserve to be more widely known, because they have a lot of interesting properties that make them useful as counterexamples in graph algorithms and graph theory. They're hard to construct and we don't have a lot of explicit descriptions of them, but that's not so important when you're using one as a counterexample.

First, what is a cage? The cages are parameterized by two numbers, \( r \) and \( g \). An \( (r,g) \)-cage is a graph that:

• is \( r \)-regular: each vertex is incident to exactly \( r \) edges,

• has girth \( g \): each cycle has at least \( g \) edges in it, and

• is as small as possible: no graph with fewer vertices is also \( r \)-regular with girth \( g \).

An example is the Petersen graph, which is the unique smallest \( 3 \)-regular graph with girth \( 5 \) and therefore is also known as the \( (3,5) \)-cage. Another, less well known, is the Robertson \( (4,5) \)-cage. Challenge: find a better layout than Robertson's, below (which I took from Wikipedia and at least shows some hints at symmetry), or than the tangled circular layouts also shown in the Wikipedia article.

I don't think it's obvious that cages exist, for all combinations of \( r \) and \( g, \) but they do. They have to be big: A simple argument based on the fact that a breadth first search of depth up to half the girth can't find any cycles shows that these graphs must have \( \Omega(r-1)^{g/2-O(1)} \) vertices, exponential in \( g \) even when \( r \) is bounded. Turning this around, if \( n \) is the number of vertices in such a graph, \( g \) can be at most \( 2\log_{r-1}n + O(1), \) only logarithmically small.

Bollobás and Szemerédi ["Girth of sparse graphs", J. Graph. Th. 2002] say that "the first good upper bound" on the size of a cage was by Erdős and Sachs in 1963. I don't know how they proved it (it's in German), but my first guess would be a form of the probabilistic method: random regular graphs have only a small number of short cycles, so probably there's some way of getting rid of them and leaving a remaining regular graph that has none at all. But as far as I know the best bounds are not probabilistic, but instead use the method of Ramanujan graphs, by Lubotzky, Phillips, and Sarnak [Combinatorica 1988]. A Ramanujan graph is a graph whose second eigenvalue is nearly as large as possible, which in turn implies that it is a good expander. In their paper, Lubotzky et al use an algebraic construction to find a family of graphs with \( g = \bigl(\tfrac{4}{3} − o(1)\bigr)\log_{r-1} n \) and they show that having such a high girth implies that the graph is a Ramanujan graph.

So we know that the girth of a cage is logarithmic in its size. But is the right constant on the logarithm \( 2 \) or \( 4/3 \)? Bollobás and Szemerédi say that it should be \( 2 \), and I don't have any reason to doubt it myself. If so, the graphs of Lubotzky et al are not themselves cages, but at least they give us an upper bound on how big cages need to be.

Beyond having high expansion, some of the other properties of cages involve high local symmetry, dense minors and high treewidth, and bad surface embeddings:

• Some of the known small cages are highly symmetric graphs, but there's no particular reason to believe that continues for larger sizes. However, they are locally symmetric: the neighborhood of every vertex looks like every other vertex, out to a radius of half the girth, just a regular tree with no cycles to be seen.

• For fixed values of \( r, \) a cage is a sparse graph. However, the cages necessarily have much denser minors. To see this, take an arbitrary spanning tree of a cage, and choose a set of equally spaced levels of the tree spaced about \( g/4 \) levels apart, such that there are about \( 4n/g \) vertices in the chosen levels. Contract the tree edges connecting each node with its nearest ancestor in a chosen level (or the root if no such ancestor exists). Because the graph has high girth, these contractions won't produce any self-loops or doubled edges, giving a minor that still has almost as many edges as it did before but with a number of vertices that has been reduced by a logarithmic factor. Even if you delete all but \( (1 + \epsilon)n \) of their edges, the same argument shows that the remaining graph will still have a dense minor. And because of their high expansion, cages also do not obey anything like the planar separator theorem, and instead have linear treewidth.

• If a graph is embedded on a surface, Euler's formula tells us the genus of the surface as a function of its number of vertices, edges, and faces. For a cage, the number of faces must be very small (each edges is in two faces but each face has logarithmically many edges), from which it follows that the genus must be linear. In fact, the minimum genus for these graphs is very close to the maximum genus of any regular graph with the same degree. They also can't be embedded nicely in the plane: Leighton proved that for bounded degree graphs, the number of crossings in any planar drawing is proportional to the square of the bisection width. Because they are expanders, cages have linear bisection width and quadratic crossing number.

Comments:

[ "01", "12", "32", "00", "2*", "30", "0*", "31", "21", "11",
  "20", "*2", "1*", "3*", "22", "*0", "10", "*1", "02" ]

    E0 = [ ((i, None), (i, j)) for i in range(4) for j in range(3) ]
    E1 = [ ((i, j), ((i+1)%4, (j+1)%3)) for i in range(4) for j in range(3) ]
    E2 = [ ((i, j), (None, j)) for i in range(4) for j in range(3) ]
    E4 = [ ((0, None), (2, None)), ((1, None), (3, None)) ]
    E = E0 + E1 + E2 + E4