Valette, Alain 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]. Reviewer: M.E.Watkins (Syracuse) Cited in 2 ReviewsCited in 4 Documents 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 Keywords:Ramanujan graph; isoperimetric constant; adjacency matrix PDFBibTeX XMLCite \textit{A. Valette}, in: Séminaire Bourbaki. Volume 1996/97. Exposés 820--834. Paris: Société Mathé\-matique de France. 247--276, Exp. No. 829 (1997; Zbl 0929.05042) Full Text: Numdam EuDML