×

zbMATH — the first resource for mathematics

Ramanujan graphs. (English) Zbl 0661.05035
A \(k\)-regular graph on \(n\) vertices is called Ramanujan graph if \(|\lambda|\leq 2\cdot\sqrt{k-1}\), where \(\lambda\) is the largest eigenvalue of its adjacency matrix. These graphs yield best known explicit expanders. The paper contains a large variety of results concerning nontrivial extremal combinatorial properties of Ramanujan and related graphs.
Reviewer: M.Křivánek

MSC:
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N.Alon,Private communication 1986.
[2] N. Alon, Eigenvalues, geometric expanders, sorting in rounds and Ramsey theory,Combinatorica,6 (1986), 207–219. · Zbl 0625.05026 · doi:10.1007/BF02579382
[3] N. Alon, Eigenvalues and expanders,Combinatorica,6 (1986), 83–96. · Zbl 0661.05053 · doi:10.1007/BF02579166
[4] B. Bollobás,Extremal graph theory, Academic Press, London 1978.
[5] L. E. Dickson, Arithmetic of quaternions,Proc. London Math. Soc. (2)20 (1922), 225–232. · doi:10.1112/plms/s2-20.1.225
[6] M. Eichler, Quaternäre quadratische Formen und die Riemannsche Vermutung für die kongruentz Zeta Funktion,Archiv. der Math. Vol. V, (1954), 355–366. · Zbl 0059.03804 · doi:10.1007/BF01898377
[7] P. Erdos andH. Sachs, Reguläre Graphen gegenebener Teillenweite mit Minimaler Knotenzahl, Wiss. Z. Univ. Halle-Wittenberg,Math. Nat. R. 12 (1963), 251–258.
[8] L.Gerritzen and N.Van der Put,Schottky groups and Mumford curves, Springer-Verlag, L. N. in Math. 817 (1980). · Zbl 0442.14009
[9] G.Hardy and E.Wright,An introduction to number theory, Oxford University Press 1978 (Fifth Edition).
[10] E.Hecke, Analytische arithmetik der positiven quadratic formen,Collected works pp. 789–898, Göttingen, 1959.
[11] A.Hofmann, On eigenvalues and colorings of graphs,in Graph theory and its applications (ed. B. Harris) Academic Press (1970), 79–91.
[12] J. Igusa, Fibre systems of Jacobian varieties III,American Jnl. of Math. 81 (1959), 453–476. · Zbl 0115.38904 · doi:10.2307/2372751
[13] Y.Ihara, Discrete subgroups of PL (2, k p ),Proc. Symp. in Pure Math. IX, AMS (1968), 272–278.
[14] W. Imrich, Explicit construction of regular graphs with no small cycles,Combinatorica 4 (1984), 53–59. · Zbl 0535.05033 · doi:10.1007/BF02579157
[15] H. Kesten, Symmetric random walks on groups,Trans. AMS 92 (1959), 336–354. · Zbl 0092.33503 · doi:10.1090/S0002-9947-1959-0109367-6
[16] M. Knesser, Strong approximation in:Algebraic Groups and Discontinuous Subgroups, Proc. Symp. Pure Math. Vol. IX, (1966), 187–196.
[17] A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan conjecture and explicit construction of expanders,Proc. Stoc. 86 (1986), 240–246.
[18] A. Lubotzky, R. Phillips, P. Sarnak, Hecke operators and distributing points onS 2 I, IIComm. Pure and Applied Math. 39 (1986), 149–186,40 (1987), 401–420. · Zbl 0619.10052 · doi:10.1002/cpa.3160390710
[19] G. A. Margulis, Graphs without short cycles,Combinatorica 2 (1982), 71–78. · Zbl 0492.05044 · doi:10.1007/BF02579283
[20] Mališev, On the representation of integers by positive definite forms,Mat. Steklov 65 (1962).
[21] A. Ogg,Modular forms and Dirichlet series, W. A. Benjamin Inc., New York 1969. · Zbl 0191.38101
[22] S. Ramanujan, On certain arithmetical functions,Trans. Camb. Phil. Soc. 22 (1916), 159–184.
[23] J. P. Serre,Trees, Springer Verlag, Berlin-Heidelberg-New York, (1980). · Zbl 0548.20018
[24] M. F.Vignéras,Arithmetique dè Algebras de Quaternions, Springer Lecture Notes; V. 800, (1980).
[25] G. L. Watson, Quadratic diophantine equations,Royal Soc. of London, Phil. Trans., A 253, 227–2 (1960).
[26] A.Weil, Sur les courbes algébriques et les varétés qui s’en déduisent,Actualites Sci. Et ind. No. 1041 (1948). · Zbl 0036.16001
[27] A. Weiss, Girths of bipartite sextet graphs,Combinatorica 4 (1984), 241–245. · Zbl 0565.05051 · doi:10.1007/BF02579225
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.