Expansion in Lifts of Graphs

Abstract

The central goal of this thesis is to better understand, and explicitly construct, expanding towers G_1,G_2,..., which are expander families with the additional constraint that G_{n+1} is a lift of G_n. A lift G of H is a graph that locally looks like H, but globally may be different; lifts have been proposed as a more structured setting for elementary explicit constructions of expanders, and there have recently been promising results in this direction by Marcus, Spielman and Srivastava [MSS13], Bilu and Linial [BL06], and Rozenman, Shalev and Wigderson [RSW06]; besides that, expansion in lifts is related to the Unique Games Conjecture (e.g., Arora et al [AKK+08]).

We develop the basic theory of spectral expanders and lifts in the generality of directed multigraphs, and give some examples of their applications. We then derive some group-theoretic structural properties of towers, and show that a large class of commonly used graph operations "respect" lifts. These two insights allow us to give a different perspective on an existing construction [RSW06], show that standard iterative constructions of expanders can be adjusted to give expander towers almost "for free", and give a new elementary construction, along the lines of Ben-Aroya and Ta-Shma [BATS11], of a fully-explicit expanding tower of almost optimal spectral expanders.