×

Ramanujan graphs and applications. (Graphes de Ramanujan et applications.) (French) Zbl 0929.05042

Séminaire Bourbaki. Volume 1996/97. Exposés 820–834. Paris: Société Mathématique de France, Astérisque. 245, 247-276, Exp. No. 829 (1997).
A finite, connected, \(k\)-valent graph is called a Ramanujan graph if every eigenvalue \(\mu\) of its adjacency matrix, with the exception of \(\mu=\pm k\), satisfies \(| \mu| \leq 2\sqrt{k-1}\). A substantial part of this expository article describes various constructions of infinite families of Ramanujan graphs.
For a graph \(X\) with vertex set \(X^0\) and \(A\subset X^0\), define \(\partial A\) to be the set of edges incident with one vertex in \(A\) and one vertex in \(X^0\backslash A\). One defines the isoperimetric constant of \(X\) by \(h(X)=\{| \partial A| /| A| :A\subset X^0; 0<| A| \leq | X^0| /2\}\). What the author calls the “fundamental problem” is to give, for a fixed positive integer \(k\), an explicit construction of an infinite family \((X_m)_{m=1}^\infty\) of finite, connected, \(k\)-valent graphs whose isoperimetric values \(h(X_m)\) are uniformly bounded away from zero. The Ramanujan graphs would provide a solution to this fundamental problem, with perimetric numbers satisfying \(h\geq(k-2\sqrt{k-1})/2\).
Upper bounds in terms of \(k\) are presented for the diameter and the independence number of a \(k\)-valent Ramanujan graph, and a lower bound is presented for the chromatic number. The article concludes with a section on further applications of Ramanujan graphs and a bibliography containing 76 items.
For the entire collection see [Zbl 0910.00034].

MSC:

05C35 Extremal problems in graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C75 Structural characterization of families of graphs
11F99 Discontinuous groups and automorphic forms
11T99 Finite fields and commutative rings (number-theoretic aspects)
11F85 \(p\)-adic theory, local fields
PDFBibTeX XMLCite
Full Text: Numdam EuDML