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.

Continue reading “The cage problem”

I want more Moore graphs…

You may have heard about the open problem on Moore graphs which is one of the most famous problems in Algebraic Graph Theory. Here is a brief synopsis…

A Moore graph is a regular graph which is extremal in the sense that its number of vertices is large compared to its degree k and diameter d. Equivalently, a Moore graph is just a regular graph with girth equal to 2d+1. There is much one can say about Moore graphs, but I just want to concentrate on the diameter 2 case; these are exactly the strongly regular graphs with \lambda=0 and \mu=1. A nice algebraic graph theory argument leads to the Hoffman-Singleton Theorem:

Theorem: Any Moore graph with diameter 2 must have degree 2, 3, 7, or 57.

The graphs with degree 2, 3, and 7 are the pentagon, Petersen graph, and Hoffman–Singleton graph, respectively, and these are the unique such diameter 2 graphs with these degrees. The last case, degree 57, is unsolved; we still do not yet know whether such a graph exists!

What we do know is that a Moore graph of diameter 2 and degree 57 is vertex-intransitive and the automorphism group has order not divisible by 4. In fact, an involutary automorphism must fix 56 points. Not much more could be said until very recently, and I want to make special mention of a recent preprint of Martin Mačaj and Jozef Širáň. They prove that the automorphism group must have size at most 375.

So what do you think? Does a Moore graph of diameter 2 and degree 57 exist?

Up ↑