Pacific Institute for the Mathematical Sciences - PIMS

A Spectral Approach to the Moore Bound

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.

4:00pm-5:00pm, WMAX 216