论文标题
关于线性的膨胀概念
On linear-algebraic notions of expansion
论文作者
论文摘要
关于有限度图扩展程序的一个基本事实是，三个膨胀概念 - 顶点扩展，边缘扩展和光谱扩展 - 都是等效的。在本文中，我们研究了这种陈述在多大程度上对于线性代数的扩展概念是正确的。 有两个良好的线性偏缘膨胀概念，即尺寸扩展（类似于图顶点膨胀）和量子膨胀（类比定义为图形光谱膨胀）。 Lubotzky和Zelmanov证明了后者意味着前者。我们证明相反的是错误：有尺寸扩展器不是量子扩张器。 此外，这种不对称性是通过以下事实来解释的：图形边缘膨胀有两个不同的线性代数类似物。其中的第一个是量子边缘扩展，这是由黑斯廷斯引入的，他被证明等同于量子扩张。我们引入了一个新的概念，称为维度边缘的扩展，我们证明这等同于维度的扩展，并且由量子边缘扩展所暗示。因此，上面的分离是由更好的分离所隐含的：尺寸边缘膨胀严格弱于量子边缘的扩展。这个新的概念还导致了Lubotzky-Zelmanov结果的新的，更模块化的证明，即量子扩张器是维数扩展器。
A fundamental fact about bounded-degree graph expanders is that three notions of expansion -- vertex expansion, edge expansion, and spectral expansion -- are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion. There are two well-studied notions of linear-algebraic expansion, namely dimension expansion (defined in analogy to graph vertex expansion) and quantum expansion (defined in analogy to graph spectral expansion). Lubotzky and Zelmanov proved that the latter implies the former. We prove that the converse is false: there are dimension expanders which are not quantum expanders. Moreover, this asymmetry is explained by the fact that there are two distinct linear-algebraic analogues of graph edge expansion. The first of these is quantum edge expansion, which was introduced by Hastings, and which he proved to be equivalent to quantum expansion. We introduce a new notion, termed dimension edge expansion, which we prove is equivalent to dimension expansion and which is implied by quantum edge expansion. Thus, the separation above is implied by a finer one: dimension edge expansion is strictly weaker than quantum edge expansion. This new notion also leads to a new, more modular proof of the Lubotzky--Zelmanov result that quantum expanders are dimension expanders.
