Moore's bound and Ramanujan complexes

Roy Meshulam
Technion - Israel Institute of Technology

The classical Moore bound asserts that the girth of a graph on n vertices with minimal degree k is at least 2 log(n)/log(k-1). We extend Moore's bound to higher dimensional simplicial complexes, and use the Ramanujan Complexes of Lubotzky, Samuels and Vishne to show that the bound is essentially optimal.
Joint work with Alex Lubotzky.

Presentation (PDF File)

Back to Expanders in Pure and Applied Mathematics