|
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.
|
|
|
|