Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-13T03:03:55.060Z Has data issue: false hasContentIssue false
  • English
  • Français

Random Lifts of Graphs: Edge Expansion

Published online by Cambridge University Press:  07 April 2006

ALON AMIT and
NATHAN LINIAL
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)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 15 , Issue 3 , May 2006, pp. 317 - 332
Copyright
2006 Cambridge University Press