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 -nets into the study of random structures. This enables us to improve (slightly) the known bounds for the edge expansion of regular graphs.
No takes yet. Share an insight, caveat, or question.
Amit et al. (2006) studied this question.