Random Lifts of Graphs: Edge Expansion
We continue the study of random lifts of graphs initiated in . 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)
1 Work supported in part by grants from the Israel Academy of Sciences and the Binational Israel–US Science Foundation.