Revised: March 28, 2024
Published: April 12, 2025
Abstract: [Plain Text Version]
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 vertex expansion of graphs) and quantum expansion (defined in analogy to spectral expansion of graphs). 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. This also answers in the negative questions of Lubotzky--Zelmanov and Dvir--Shpilka on the relation between dimension expansion and Kazhdan's property T.
Moreover, this asymmetry is explained by the fact that there are two distinct linear-algebraic analogues of edge expansion of graphs. 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.
Licensed under a Creative Commons Attribution License (CC-BY)