Discrete Mathematics and Optimization Seminar
Mar. 15th, 2010
Ramanujan graphs of large girth
Xavier Dahan
Kyushu University
Ramanujan graphs are optimal (spectral) expanders. We will first introduce the concept of expansion in a regular graph, then define expanders, that have dozens of applications in Computer and Information science [2]. We will review the construction of [1], i.e. Cayley graphs on discrete quaternionic groups, then show what is changing when using octonions instead. We obtain families of regular graphs with a larger girth, and hence with the largest girth known.

(joint work with J.-P. Tillich)

[1] Lubotzsky, Philips and Sarnak. Ramanujan grpahs. Coombinatorica, 1988.
[2] Hoory, Linial and Wigderson. Expander graphs and their applications, Bull of the AMS, 2006.