Expansion in Lifts of Graphs
Expansion in Lifts of Graphs
复制标题
图提升的扩展
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Aleksandar Makelov
中科院分区：
文献类型：
--
作者：
Aleksandar Makelov
该论文的中心目标是更好地理解，并明确地构建塔，G1，G2。局部看起来像H，但可能是全球不同的； Marcus，Spielman和Srivastava [MSS13]，Bilu和Linial [BL06]以及Rozenman，Shalev和Wigderson [RSW06] ]。塔的属性，并表明一类常用的图形操作“尊重”升降机。给扩展塔几乎“免费”，并沿Ben-Aroya和Ta-shma [Bats11]的新基本结构，这是一个完全解释的扩展塔，几乎是最佳的光谱扩展器1。
The central goal of this thesis is to better understand, and explicitly construct, expanding towers G1,G2, . . ., which are expander families with the additional constraint that Gn+1 is a lift of Gn . A lift G of H is a graph that locally looks like H , but may be globally di erent; 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 di erent 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. 1As required by the Computer Science concentration thesis guidelines.