Expansion in Lifts of Graphs
Citation
Makelov, Aleksandar A. 2015. Expansion in Lifts of Graphs. Bachelor's thesis, Harvard College.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.
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:14398532
Collections
- FAS Theses and Dissertations [6136]
Contact administrator regarding this item (to report mistakes or request changes)