scientific article; zbMATH DE number 1182557
Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) (p)-adic theory, local fields (11F85) Discontinuous groups and automorphic forms (11F99) Finite fields and commutative rings (number-theoretic aspects) (11T99)
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].
- Ramanujan type graphs and bigraphs.
- Weighted expanders and the anisotropic Alon-Boppana theorem
- Ramanujan grammar and Cayley trees
- A connection between a question of Bermond and Bollobás and Ramanujan graphs
- Diameter of Ramanujan graphs and random Cayley graphs
- Expanding graphs, Ramanujan graphs, and 1-factor perturbations
- Communication constraints in the average consensus problem
- Ramanujan Diagrams
- scientific article; zbMATH DE number 2042680 (Why is no real title available?)
- scientific article; zbMATH DE number 1465652 (Why is no real title available?)
- Ramanujan hypergraphs and Ramanujan geometries
- Ramanujan complexes and high dimensional expanders
- Ramanujan graphs arising as weighted Galois covering graphs
- scientific article; zbMATH DE number 7623647 (Why is no real title available?)
- scientific article; zbMATH DE number 5679781 (Why is no real title available?)
- On the Ramanujancy of Heisenberg graphs over rings of degree 6 or more
- Isoperimetric numbers of regular graphs of high degree with applications to arithmetic Riemann surfaces
- Fractional graph expanders and network dynamics: spectral properties and diffusion with applications to quantum cryptography
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)