Combinatorics, Probability and Computing



Paper

Random Lifts of Graphs: Edge Expansion


ALON AMIT a1 and NATHAN LINIAL a2 1
a1 Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel (e-mail: alona@math.huji.ac.il)
a2 Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel (e-mail: nati@cs.huji.ac.il)

Article author query
amit a   [Google Scholar] 
linial n   [Google Scholar] 
 

Abstract

We continue the study of random lifts of graphs initiated in [4]. Here we study the possibility of generating graphs with high edge expansion as random lifts. Along the way, we introduce the method of $\epsilon$-nets into the study of random structures. This enables us to improve (slightly) the known bounds for the edge expansion of regular graphs.

(Received March 27 2000)
(Revised December 22 2002)



Footnotes

1 Work supported in part by grants from the Israel Academy of Sciences and the Binational Israel–US Science Foundation.