The cage problem
Guillermo Pineda-Villavicencio visited Perth from the University of Ballarat for the previous two weeks and introduced me to the cage problem so I thought I would write a post setting out what I have learnt to get it all straight in my mind.
The girth g of a graph is the length of the shortest cycle . The cage problem is to find the smallest number n(k,g) of vertices for a regular graph of valency k and girth g. A valency k graph of girth g with n(k,g) vertices is referred to as a (k,g)-cage. A (k,g)-cage is not necessarily unique. In fact there are 18 (3,9)-cages and these have order 58.
The Petersen graph is the (3,5)-cage and has order 10. The Heawood graph, (the point-line incidence graph of the Fano plane) is the (3,6)-cage and has order 14. In fact the point-line incidence graph of a projective plane of order q is a (q+1,6)-cage. The Tutte-Coxeter graph (the point-line incidence graph of the smallest generalised quadrangle W(2)) is the (3,8)-cage and is sometimes called Tutte’s 8-cage. The point-line incidence graph of a generalised quadrangle of order (q,q) is a (q+1,8)-cage.
The actual value of n(k,g) has only been determined for a small number of values of k and g. The latest knowledge of bounds on n(k,g) is given in these tables at the Combinatorics Wiki. There is also a good dynamic survey by Geoffrey Exoo and Robert Jajcay at the Electronic Journal of Combinatorics.
In some sense the cage problem is the opposite to the problem of finding Moore graphs discussed by John in an earlier post which are the extremal graphs for the degree-diameter problem, that is, the problem of finding the largest graphs of a given valency and diameter.
If has valency k then for each the number of vertices of at distance i from a vertex v is . Hence for g odd we have
The number of vertices at distance i from an edge is for each . Hence for g even we get
The graphs which meet these bounds are the Moore graphs mentioned previously. These bounds give us an initial lower bound for n(k,g).
There is a construction of Sachs (Regular graphs with given girth and restricted circuits, J. London Math. Society 38 (1963) 423-429) which shows that for all , there exists a k-regular graph of girth g. Here I will give a construction of Biggs which shows that there is a finite k-regular Cayley graph of girth at most g. First I need to discuss Cayley graphs.
Given a group G and subset S such that and , the Cayley graph Cay(G,S), is the graph with vertices the elements of G and two elements x and y are adjacent if and only if . The condition guarantees that the the graph does not contain any loops while implies that if and only if and so our graph is indeed an undirected graph. At times it is convenient to think of each edge labelled by the element of S that yields the adjacency of its two end vertices. The graph is connected if and only is . Now G acts transitively by right multiplication on the vertices of our Cayley graph and preserves adjacency. Thus we obtain a regular group of automorphisms. Indeed a graph is isomorphic to a Cayley graph if and only if its automorphism group Aut() contains a regular subgroup.
Note that the neighbours of in Cay(G,S) are the elements of S and the neighbours of an element x are the elements sx, for . Moreover, there is a cycle of length s in Cay(G,S) if and only if there is a word with : since Cay(G,S) is vertex-transitive it is sufficient to find such a cycle starting at . Given the word , we get a cycle . Conversely, given a path starting at we get a word of length s by multiplying together the elements of S labelling the edges of the cycle. This path will be a cycle if the word is equal to .
Now for the construction of Biggs: take a tree T of depth g-1 such that all vertices at depth less than g-1 have valency k. Colour the edges of T with k colours so that no two edges adjacent to a common vertex have the same colour. For each colour , define an involutory permutation of the vertices of T such that interchanges v and w if and only if v and w are joined by an edge coloured . Now let S be the set of k involutions obtained and G be the group generated by S (G is finite as it is a group of permutations of a finite set). Then Cay(G,S) is a k-regular graph. Now if the girth of our Cayley graph was then we would have a word with each . However, the image of the root of our tree T under is a vertex at distance s<g from the root, contradicting being the identity permutation. Thus Cay(G,S) has girth at least g.
Cayley graphs have been used to construct cages and also for some values of (k,g) give graphs with the lowest known number of vertices. For example the smallest known graph of valency 3 and girth 13 is a Cayley graph for AGL(1,17). If you want to construct a Cayley graph of valency k and girth g the general idea is to find a group with k generators such that no word of length less than g in the generators evaluates to the identity. One thing to note here is that a Cayley graph of an abelian group has girth at most four as for any two elements x, y in the group, .
Another method that has been fruitful in constructing cages or graphs holding the record is voltage assignments. We start with a multigraph , possibly with loops such that each vertex has valency k, and a group G. The graph is referred to as the base graph and G the voltage group. A voltage assignment is a labelling of the arcs of by elements of G such that if an arc is labelled by g then the reverse arc is labelled by . The lift of is then the graph with vertex set such that two vertices (v,g) is adjacent to (w,h) if and only if v is adjacent to w in and the arc from v to w is labelled by . The group G acts semiregularly as a group of automorphisms of the lift as an element maps the vertex (v,g) to (v,gk).
For an example, let be the graph with two vertices u and v joined by a single edge and with a loop on each vertex. We use as the voltage group and label the edge between u and v by 0, the loop at u by 1 and the loop at v by 2. The vertices of the lift are all pairs (u,i) and (v,i) with . Moreover, (u,i) is adjacent to (u,j) when while (v,i) is adjacent to (v,j) when . Finally, (u,i) is adjacent to (v,i). You may recognise this graph as the Petersen graph.
Next I discuss the notion of a family with large girth due to Biggs. Our discussion is along the lines of the Dynamic Survey. Using the Moore bounds, we see that the least number of vertices of a k-regular graph of of girth g is roughly and hence if n is the number of vertices of a k-regular graph of girth g we have . We say that a family of k-regular graphs with girth and vertices is a family with large girth if there is a constant such that . We have just seen that is at most 2. The sextet graphs of Biggs and Hoare have as do the Ramanujan graphs of Lubotsky, Phillips and Sarnak.