2009 Discrete Maths Seminar - 02

The so called "Moore Bound" is one of the great puzzles of graph theory. It is an upper bound on the girth of a d-regular graph on n vertices; it is almost immediate, and appeared in publication roughly 50 years ago. However, this bound has only been improved by an additive factor of -1 or -2 for any d > 2 and n. We focus on the problem of fixing d and letting n tend to infinity. The Moore Bound gives an upper bound of roughly 2 log(n)/log(d-1), whereas the highest girth known is roughly (4/3) log(n)/log(d-1) (for the LPS expanders, for certain values of d and n; random graphs do worse). We describe a spectral approach to improving the Moore Bound with abelian lifts. Our main result is to describe a edge colouring problem, such that a significant improvement over a greedy colouring result would lead to an asymptotic improvement in the Moore Bound. (Unfortunately, we have no results on the colouring problem at present...). This is joint work with Nati Linial.