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 \Gamma 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 \Gamma has valency k then for each i\leq \lfloor \frac{(g-1)}{2}\rfloor the number of vertices of \Gamma at distance i from a vertex v is k(k-1)^{i-1}. Hence for g odd we have

n(k,g)\geq 1+k+k(k-1)+k(k-1)^2+\ldots+k(k-1)^{(g-3)/2}

The number of vertices at distance i from an  edge is 2(k-1)^i for each i\leq\lfloor \frac{(g-1)}{2}\rfloor. Hence for  g even we get

n(k,g)\geq 2(1+(k-1)+(k-1)^2+\ldots+(k-1)^{(g-2)/2})

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 k,g\geq 3, 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 S^{-1}=S and 1\notin S, 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 xy^{-1}\in S.  The condition 1\notin S guarantees that the the graph does not contain any loops while S^{-1}=S implies that xy^{-1}\in S if and only if yx^{-1}\in S 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 \langle S\rangle =G.  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 \Gamma is isomorphic to a Cayley graph if and only if its automorphism group Aut(\Gamma) contains a regular subgroup.

Note that the neighbours of 1_G in Cay(G,S) are the elements of S and the neighbours of an element x are the elements sx, for s\in S.  Moreover, there is a cycle of length s in Cay(G,S) if and only if there is a word w_1w_2\ldots w_s=1_G with w_i\in S: since Cay(G,S) is vertex-transitive it is sufficient to find such a cycle starting at 1_G. Given the word w_1w_2\ldots w_s=1_G, we get a cycle 1_G, w_s, w_{s-1}w_s,w_{s-2}w_{s-1}w_s,\ldots, w_2w_3\ldots w_{s}. Conversely, given a path starting at 1_G 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 1_G.

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 \alpha, define an involutory permutation  i_\alpha of the vertices of T such that i_\alpha interchanges v and w if and only if v and w are joined by an edge coloured \alpha. 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 s<g then we would have a word w_1w_2\ldots w_s=1_G with each w_i\in S. However, the image of the root of our tree T under w_1w_2\ldots w_s is a vertex at distance s<g from the root,  contradicting w_1w_2\ldots w_s 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, xyx^{-1}y^{-1}=1.

Another method that has been fruitful in constructing cages or graphs holding the record is voltage assignments. We start with a multigraph \Gamma, possibly with loops such that each vertex has valency k, and a group G. The graph \Gamma is referred to as the base graph and G the voltage group. A voltage assignment is a labelling of the arcs of \Gamma by elements of G such that if an arc is labelled by g then the reverse arc is labelled by g^{-1}. The lift of \Gamma is then the graph with vertex set V\Gamma \times G such that two vertices (v,g) is adjacent to (w,h) if and only if v is adjacent to w in \Gamma and the arc from v to w is labelled by hg^{-1}. The group G acts semiregularly as a group of automorphisms  of the lift as an element k\in G maps the vertex (v,g) to (v,gk).

For an example, let \Gamma be the graph with two vertices u and v joined by a single edge and with a loop on each vertex. We use \mathbb{Z}_5 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 i\in \mathbb{Z}_5. Moreover, (u,i) is adjacent to (u,j) when i-j=\pm 1 while (v,i) is adjacent to (v,j) when i-j=\pm 2. 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 (k-1)^{g/2} and hence if n is the number of vertices of a k-regular graph of girth g we have g\leq 2log_{k-1}(n).  We say that a family \{\Gamma_i\} of k-regular graphs with girth g_i and n_i vertices is a family with large girth if there is a constant \gamma such that g_i\geq \gamma log_{k-1}(n_i). We have just seen that \gamma is at most 2. The sextet graphs of Biggs and Hoare have \gamma \geq 4/3 as do the Ramanujan graphs of Lubotsky, Phillips and Sarnak.

Author: Michael Giudici


One thought on “The cage problem”

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s