Random Lifts of Graphs: Edge Expansion

Alon Amit, Nathan Linial

Type: Article

Publication Date: 2006-04-07

Citations: 50

DOI: https://doi.org/10.1017/s0963548305007273

View Publication

Locations

Combinatorics Probability Computing - View

Similar Works

Action	Title	Year	Authors
+	$\delta$-Connectivity in Random Lifts of Graphs	2017	Shashwat Silas
+ PDF Chat	Random Lifts of Graphs are Highly Connected	2013	Marcin Witkowski
+ PDF Chat	Cutoff for random lifts of weighted graphs	2019	Guillaume Conchon--Kerjan
+	Connectivity in Random Lifts of Graphs: New Techniques and Results.	2016	Shashwat Silas
+ PDF Chat	Topological Minors in Typical Lifts	2024	Matija Bucić Micha Christoph Alp Müyesser Raphael Steiner
+	Random Lifts Of Graphs: Perfect Matchings	2005	Nathan Linial Eyal Rozenman
+	Small Lifts of Expander Graphs are Expanding.	2013	Naman Agarwal Alexandra Kolla Vivek Madan
+	Random Regular Graphs	2000	Svante Janson Tomasz Łuczak Andrzej Ruciński
+	Random Lifts Of Graphs: Network Robustness Based On The Estrada Index	2012	Yilun Shang
+	Random Graphs, Retractions and Clique Graphs	2008	F. Larrión M.A. Pizaña Rafael Villarroel-Flores
+	Randomly Generated Subgroups of the Symmetric Group and Random Lifts of Graphs	2016	Shashwat Silas
+	Randomly Generated Subgroups of the Symmetric Group and Random Lifts of Graphs	2016	Shashwat Silas
+	Random graphs	2010	Béla Bollobás
+	Random lifts of graphs	2001	Alon Amit Nathan Linial Jiřı́ Matoušek Eyal Rozenman
+ PDF Chat	Tight products and graph expansion	2011	Amit Daniely Nathan Linial
+	Random graphs	2008	Alain Barrat Marc Barthélemy Alessandro Vespignani
+	Pseudo-random graphs	2005	Michael Krivelevich Benny Sudakov
+	Tight products and Expansion	2010	Amit Daniely Nathan Linial
+	Hamilton Cycles in Random Lifts of Graphs	2013	Tomasz Łuczak Łukasz Witkowski Marcin E. Witkowski
+	Hamilton Cycles in Random Lifts of Graphs	2013	Tomasz Łuczak Łukasz Witkowski Marcin Witkowski

Works That Cite This (43)

Action	Title	Year	Authors
+	The chromatic number of random lifts of	2009	Babak Farzad Dirk Oliver Theis
+ PDF Chat	Expansion of random graphs: new proofs, new results	2014	Doron Puder
+ PDF Chat	Tight products and graph expansion	2011	Amit Daniely Nathan Linial
+	Lifts, Discrepancy and Nearly Optimal Spectral Gap*	2006	Yonatan Bilu Nathan Linial
+	Expander Graphs and their Applications Draft-not for distribution	2006	Shlomo Hoory Nathan Linial Avi Wigderson
+ PDF Chat	Spectra of lifted Ramanujan graphs	2011	Eyal Lubetzky Benny Sudakov Van Vu
+	Hamilton cycles in random lifts of graphs	2015	Tomasz Łuczak Łukasz Witkowski Marcin Witkowski
+	Expanders in power law graphs	2018	Anton Cherniavskyi
+ PDF Chat	The spectrum of random $k$-lifts of large graphs (with possibly large $k$)	2010	Roberto I. Oliveira
+	Hamilton cycles in random lifts of graphs	2006	K. Burgin Prasad Chebolu Colin Cooper Alan Frieze

Works Cited by This (7)

Action	Title	Year	Authors
+	Tools from higher algebra	1996	Noga Alon
+	Random Graph Coverings I: General Theory and Graph Connectivity	2002	Alon Amit Nathan Linial
+	Explicit expanders and the Ramanujan conjectures	1986	Alexander Lubotzky Ralph S. Phillips Peter Sarnak
+	λ1, Isoperimetric inequalities for graphs, and superconcentrators	1985	Noga Alon Vitali Milman
+	The Isoperimetric Number of Random Regular Graphs	1988	Béla Bollobás
+	On the second eigenvalue of random regular graphs	1989	Joel Friedman J. Kahn Endre Szemerédi
+ PDF Chat	Permutation Pseudographs and Contiguity	2002	Catherine Greenhill Svante Janson Jeong Han Kim Nicholas Wormald