Makelov, Aleksandar2015-04-092015-052015-04-082015Makelov, Aleksandar A. 2015. Expansion in Lifts of Graphs. Bachelor's thesis, Harvard College.http://nrs.harvard.edu/urn-3:HUL.InstRepos:14398532The 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.application/pdfenMathematicsComputer ScienceThesis or Dissertation2015-04-09