scientific article; zbMATH DE number 1182557

From MaRDI portal
Publication:4400627





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











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4400627)