Hostname: page-component-7c8c6479df-hgkh8 Total loading time: 0 Render date: 2024-03-27T14:12:41.812Z Has data issue: false hasContentIssue false

Random Lifts of Graphs: Edge Expansion

Published online by Cambridge University Press:  07 April 2006

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

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.

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)