License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.78
URN: urn:nbn:de:0030-drops-175819
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17581/
Go to the corresponding LIPIcs Volume Portal

Kaufman, Tali ; Tessler, Ran J.

Garland’s Technique for Posets and High Dimensional Grassmannian Expanders

pdf-format:
LIPIcs-ITCS-2023-78.pdf (0.7 MB)

Abstract

Local to global machinery plays an important role in the study of simplicial complexes, since the seminal work of Garland [Garland, 1973] to our days. In this work we develop a local to global machinery for general posets. We show that the high dimensional expansion notions and many recent expansion results have a generalization to posets. Examples are fast convergence of high dimensional random walks generalizing [Kaufman et al., 2020], [Alev and Lau, 2020], an equivalence with a global random walk definition, generalizing [Dikstein et al., 2018] and a trickling down theorem, generalizing [Oppenheim, 2018].
In particular, we show that some posets, such as the Grassmannian poset, exhibit qualitatively stronger trickling down effect than simplicial complexes.
Using these methods, and the novel idea of posetification to Ramanujan complexes [Lubotzky et al., 2005a], [Lubotzky et al., 2005b], we construct a constant degree expanding Grassmannian poset, and analyze its expansion. This it the first construction of such object, whose existence was conjectured in [Dikstein et al., 2018].

BibTeX - Entry

@InProceedings{kaufman_et_al:LIPIcs.ITCS.2023.78,
  author =	{Kaufman, Tali and Tessler, Ran J.},
  title =	{{Garland’s Technique for Posets and High Dimensional Grassmannian Expanders}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{78:1--78:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17581},
  URN =		{urn:nbn:de:0030-drops-175819},
  doi =		{10.4230/LIPIcs.ITCS.2023.78},
  annote =	{Keywords: High dimensional Expanders, Posets, Grassmannian, Garland Method}
}

Keywords: High dimensional Expanders, Posets, Grassmannian, Garland Method
Collection: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI