Ilan is 60

Finding and Using Expanders in Locally Sparse Graphs (Michael Krivelevich)

Abstract: Our main goal is to find large expanders in locally sparse graphs. For constants c1 > c2 > 1, 0 < a < 1, a graph G on n vertices is called a (c1, c2, a)-graph if it has at least c1*n edges, but every vertex subset W of size at most a*n spans less than c2*|W| edges. (Putting it informally, the local density of G is sizably smaller than its global density.) For example, sparse random graphs G drawn from G(n, C/n) are typically locally sparse.

We will show that every (c1, c2, a)-graph G with bounded degrees contains a spanning expander of linear order. We will also discuss algorithmic aspects of the proof.

Time permitting, we will discuss applications of this result to problems about embedding graph minors, and to positional games.