On the structure of asymptotic expanders

Ana Khukhro, Kang Li, Federico Vigolo, Jiawen ZhangAdvances 2021 · DOI

TL;DR

This paper introduces a new structural theorem for "asymptotic expanders," a class of geometric objects that generalize expanders. The authors show these objects can be "exhausted" by expanders, leading to a deeper understanding of their properties and providing new counterexamples to a major conjecture in geometric analysis.

What Problem Does This Paper Address?

The paper delves into the fascinating world of "asymptotic expanders," which are geometric structures that exhibit some, but not all, of the remarkable properties of "expanders." Expanders are graphs with excellent connectivity properties, making them useful in areas like network design and theoretical computer science. Asymptotic expanders are a more relaxed notion, allowing for certain "imperfections" that expanders don't tolerate.

A key motivation for this work comes from the study of "uniform Roe algebras," which are algebraic structures that encode coarse geometric information about metric spaces. A central question in this area is understanding when certain operators, like the "averaging projection," belong to these algebras. This question is closely tied to the "coarse Baum-Connes conjecture," a significant open problem in geometric topology and operator algebras. The authors aim to characterize asymptotic expanders and use this characterization to shed light on these algebraic structures and the conjecture.

Methods

The core of the paper lies in its "Structure Theorems" for asymptotic expanders. The authors develop a way to view asymptotic expanders as being "exhausted" by a sequence of actual expanders. This means that within an asymptotic expander, one can find increasingly large substructures that behave like expanders.

Specifically, for graphs with uniformly bounded degrees, they prove that being an asymptotic expander is equivalent to admitting a "uniform exhaustion by expanders." For more general metric spaces, they establish a similar, though slightly more technical, structure theorem. These theorems are built upon a key lemma concerning "c-Følner sets" and their boundaries, which allows them to control the "boundary" of subsets within these spaces.

The paper also leverages existing results from the literature, particularly concerning coarse embeddings into Banach spaces and the properties of Roe algebras and quasi-local operators.

Datasets

Not discussed in the paper. The paper deals with theoretical mathematical structures rather than empirical data.

Key Insights and Ideas

  • Asymptotic expanders are "almost" expanders: The paper demonstrates that asymptotic expanders can be systematically decomposed into or "exhausted" by actual expanders. This provides a powerful new way to understand their internal structure.
  • A bridge between algebra and geometry: The work establishes a crucial link between the algebraic notion of asymptotic expanders and the analytic properties of uniform Roe algebras. Specifically, the averaging projection belongs to the uniform Roe algebra if and only if the underlying space is a sequence of asymptotic expanders.
  • New counterexamples to a major conjecture: By connecting asymptotic expanders to the existence of "non-compact ghost projections" in Roe algebras, the authors generate a new class of counterexamples to the coarse Baum-Connes conjecture. Crucially, these counterexamples do not rely on the presence of a "spectral gap," a common feature of previous counterexamples.
  • Robustness of asymptotic expanders: The paper highlights that asymptotic expanders are more robust than standard expanders under certain types of "perturbations," making them a potentially more versatile tool.

Key Results

  • Structure Theorem for Asymptotic Expanders: The paper proves that a sequence of finite graphs with uniformly bounded degrees is a sequence of asymptotic expanders if and only if it admits a uniform exhaustion by expanders. A similar theorem is established for general finite metric spaces.
  • Algebraic Characterization: The averaging projection of a coarse disjoint union of metric spaces belongs to its uniform Roe algebra if and only if the sequence of spaces is a sequence of asymptotic expanders.
  • Counterexamples to the Coarse Baum-Connes Conjecture: The authors construct uncountably many non-coarsely-equivalent families of asymptotic expander graphs that are not expanders and violate the coarse Baum-Connes conjecture. These counterexamples do not necessarily have spectral gaps.
  • No Coarse Embeddings into Certain Banach Spaces: Asymptotic expanders with uniformly bounded geometry cannot be coarsely embedded into certain classes of Banach spaces (specifically, those in the class $C_0$).

Limitations and Future Work

The paper acknowledges that the definition of asymptotic expanders is a relaxation of expanders, and while this leads to new insights and counterexamples, it also means that some of the well-established characterizations of expanders do not directly apply.

The authors pose several open questions for future research:

  • Spectral Characterization: Is there a characterization of asymptotic expanders in terms of spectra, analogous to how expanders are characterized by the spectral gap of the Laplacian?
  • C*-Algebraic Characterization of Expanders: Can expanders be characterized by a C*-algebraic condition in general?
  • Equivalence of Asymptotic and Standard Expanders: For which classes of graphs are asymptotic expanders equivalent to standard expanders?
  • Banach Space Embeddings: Do the classes of Banach spaces that do not admit coarse embeddings of expanders and asymptotic expanders coincide?

The paper also suggests that asymptotic expanders might play a role in dynamical systems due to their connection with strong ergodicity.

Summary updated

BibTeX
@inproceedings{khukhro2021structure,
  author = {Ana Khukhro and Kang Li and Federico Vigolo and Jiawen Zhang},
  title = {{On the structure of asymptotic expanders}},
  booktitle = {Advances},
  year = {2021},
  doi = {10.1016/j.aim.2021.108073},
}

Loading related content...

Figure