## 2009 Discrete Maths Seminar - 02

- Date: 02/03/2009

University of British Columbia

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