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.
%0 Journal Article
%1 amit06
%A AMIT, ALON
%A LINIAL, NATHAN
%D 2006
%I Cambridge University Press
%J Combinatorics, Probability and Computing
%K graph.theory lift
%N 3
%P 317--332
%R 10.1017/s0963548305007273
%T Random Lifts of Graphs: Edge Expansion
%V 15
%X 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.
@article{amit06,
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.},
added-at = {2016-10-29T16:08:43.000+0200},
author = {AMIT, ALON and LINIAL, NATHAN},
biburl = {https://www.bibsonomy.org/bibtex/2aa2e05ad993e5d22777af404db46642a/ytyoun},
doi = {10.1017/s0963548305007273},
interhash = {649d2fcdcce90bea62f1b3528b931138},
intrahash = {aa2e05ad993e5d22777af404db46642a},
journal = {Combinatorics, Probability and Computing},
keywords = {graph.theory lift},
month = apr,
number = 3,
pages = {317--332},
publisher = {Cambridge University Press},
timestamp = {2016-10-29T16:08:43.000+0200},
title = {Random Lifts of Graphs: Edge Expansion},
volume = 15,
year = 2006
}