On the second eigenvalue of random regular graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the second eigenvalue of random regular graphs

Full text

Pdf (1.10 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-first annual ACM symposium on Theory of computing table of contents

Seattle, Washington, United States

Pages: 587 - 598

Year of Publication: 1989

ISBN:0-89791-307-8

Authors

J. Friedman	Department of Computer Science, Princeton University, Princeton, NJ
J. Kahn	Dept. of Mathematics and Center for O. R., Rutgers University, New Brunswick, NJ
E. Szemerédi	Dept. of Computer Science, Rutgers University, New Brunswick, NJ and Mathematical Institute of the Hungarian Academy of Sciences

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 122, Citation Count: 16

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/73007.73063 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Alo86	N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	BS87	Andrei Broder and E},i Shamir. On the s.~cond eigenvalue of random regular graphs. In 18th Annual Symposium on Foundations of Computer Science, pages 286-294, 1987.
	FK81	Z. Fiiredi and J. Komlds. Tile eigenvalues of random symmetric matrices. Uombinatorica, 1(3):233-241, 1981.
	Fri88	J. Friedman. On the second eigenvalue 8nd random walks in random d-regular graphs. Technical Report CS-TR-172-88, Princel,on University, August 1988.
	Gem80	S. Geman. A limit theorem for the norm of random matrices. Alan. of Prob., 8(2):2~i2- 261, 1980.
	LPS86	A Lubotzky , R Phillips , P Sarnak, Explicit expanders and the Ramanujan conjectures, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.240-246, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12154]
	Mar87	G. Margulis. Manuscript in Russian on graphs with large girth, 1987.
	McK81	B. McKay. The expected eigenvalue distribution of a large regular graph. Lin. Alg. Appl., 40:203-216, 1981.
	MS80	Vitali D Milman , Gideon Schechtman, Asymptotic theory of finite dimensional normed spaces, Springer-Verlag New York, Inc., New York, NY, 1986
	SS87	E. Shamir , J. Spencer, Sharp concentration of the chromatic number on random graphs Gn,p, Combinatorica, v.7 n.1, p.121-129, Jan. 1987 [doi>10.1007/BF02579208]
	Tan84	R.M. Tanner. Explicit concentrators from generalized n-gons. SIAM J. Alg. Disc. Methods, 5:287-293, 1984.
	Wig55	E. Wigner. Characteristic vectors of bordered matrices with infinite dimensions. Annals of Math., 63(3):548-564, 1955.

CITED BY 16

	Alan M. Frieze , Lei Zhao, Optimal construction of edge-disjoint paths in random regular graphs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.346-355, January 17-19, 1999, Baltimore, Maryland, United States
	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, Existence and construction of edge disjoint paths on expander graphs, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1992, Victoria, British Columbia, Canada
	Noga Alon , Benny Sudakov , Uri Zwick, Constructing worst case instances for semidefinite programming based approximation algorithms, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.92-100, January 07-09, 2001, Washington, D.C., United States
	Andrei A. Broder , Alan M. Frieze , Stephen Suen , Eli Upfal, Optimal construction of edge-disjoint paths in random graphs, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.603-612, January 23-25, 1994, Arlington, Virginia, United States
	Noga Alon , Nabil Kahale, A spectral technique for coloring random 3-colorable graphs (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.346-355, May 23-25, 1994, Montreal, Quebec, Canada
	Abraham Flaxman, A spectral technique for random satisfiable 3CNF formulas, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Joel Friedman, A proof of alon's second eigenvalue conjecture, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Omer Reingold, Undirected ST-connectivity in log-space, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Amin Coja-Oghlan , Cristopher Moore , Vishal Sanwalani, MAX k-CUT and approximating the chromatic number of random graphs, Random Structures & Algorithms, v.28 n.3, p.289-322, May 2006
	Elchanan Mossel , Sébastien Roch, Slow emergence of cooperation for win-stay lose-shift on trees, Machine Learning, v.67 n.1-2, p.7-22, May 2007
	Alon Amit , Nathan Linial, Random Lifts of Graphs: Edge Expansion, Combinatorics, Probability and Computing, v.15 n.3, p.317-332, May 2006
	Amin Coja-oghlan, The Lovász Number of Random Graphs, Combinatorics, Probability and Computing, v.14 n.4, p.439-465, July 2005
	Noga Alon, On the Edge-Expansion of Graphs, Combinatorics, Probability and Computing, v.6 n.2, p.145-152, June 1997
	Anirban Dasgupta , John Hopcroft , Ravi Kannan , Pradipta Mitra, Spectral clustering with limited independence, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1036-1045, January 07-09, 2007, New Orleans, Louisiana
	Alan M. Frieze , Lei Zhao, Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs, Combinatorics, Probability and Computing, v.9 n.3, p.241-263, May 2000
	Omer Reingold, Undirected connectivity in log-space, Journal of the ACM (JACM), v.55 n.4, p.1-24, September 2008