分野別セミナー

This work presents a construction of some families of regular graphs that have two aspects:
1) they are "Ramanujan", which means that their adjacency matrices have small eigenvalues, besides the largest one(s).
2) they have a large "girth" (there is no short walk that permits to come back to the starting vertex of the walk).
Point 1) implies that they are good "expander graphs": these graphs have numerous applications in Computer & Information
science, and more recently in "pure" mathematics as well (Cf. [2,3]).
Point 2) is related to a very classical upper bound in graph theory, the "Moore bound".
It follows from an elementary counting argument, but it is not known how tight is this bound.
The large girth graphs constructed here, show that the Moore bound is not too bad.
We follow the strategy of the landmark paper [1], but use octonions instead of quaternions.
In the talk, we will review the basic concepts of spectral graph theory and expanders,
then focus on the more mathematical aspects of this work. (Ramanujan conjecture and elementary arithmetic
of octonions)
[1] Ramanujan graphs. Lubotzky-Philips-Sarnak, Combinatorica, 1988.
[2] Expander graphs and their applications. Linial, Hoory, Wigderson, Bull. of the AMS, 2006.
[3] Video lecture of Avi Wigderson (IAS, Princeton) for an overview of expanders
http://video.ias.edu/pseudo2010/wigderson1