# High-dimensional expansion and crossing numbers of simplicial complexes

Wild P. 2022. High-dimensional expansion and crossing numbers of simplicial complexes. Institute of Science and Technology (ISTA).

High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes 5.09 MB

Thesis | PhD | Published | English
Author
Supervisor
Department
Series Title
ISTA Thesis
Abstract
In this dissertation we study coboundary expansion of simplicial complex with a view of giving geometric applications. Our main novel tool is an equivariant version of Gromov's celebrated Topological Overlap Theorem. The equivariant topological overlap theorem leads to various geometric applications including a quantitative non-embeddability result for sufficiently thick buildings (which partially resolves a conjecture of Tancer and Vorwerk) and an improved lower bound on the pair-crossing number of (bounded degree) expander graphs. Additionally, we will give new proofs for several known lower bounds for geometric problems such as the number of Tverberg partitions or the crossing number of complete bipartite graphs. For the aforementioned applications one is naturally lead to study expansion properties of joins of simplicial complexes. In the presence of a special certificate for expansion (as it is the case, e.g., for spherical buildings), the join of two expanders is an expander. On the flip-side, we report quite some evidence that coboundary expansion exhibits very non-product-like behaviour under taking joins. For instance, we exhibit infinite families of graphs $(G_n)_{n\in \mathbb{N}}$ and $(H_n)_{n\in\mathbb{N}}$ whose join $G_n*H_n$ has expansion of lower order than the product of the expansion constant of the graphs. Moreover, we show an upper bound of $(d+1)/2^d$ on the normalized coboundary expansion constants for the complete multipartite complex $[n]^{*(d+1)}$ (under a mild divisibility condition on $n$). Via the probabilistic method the latter result extends to an upper bound of $(d+1)/2^d+\varepsilon$ on the coboundary expansion constant of the spherical building associated with $\mathrm{PGL}_{d+2}(\mathbb{F}_q)$ for any $\varepsilon>0$ and sufficiently large $q=q(\varepsilon)$. This disproves a conjecture of Lubotzky, Meshulam and Mozes -- in a rather strong sense. By improving on existing lower bounds we make further progress towards closing the gap between the known lower and upper bounds on the coboundary expansion constants of $[n]^{*(d+1)}$. The best improvements we achieve using computer-aided proofs and flag algebras. The exact value even for the complete $3$-partite $2$-dimensional complex $[n]^{*3}$ remains unknown but we are happy to conjecture a precise value for every $n$. %Moreover, we show that a previously shown lower bound on the expansion constant of the spherical building associated with $\mathrm{PGL}_{2}(\mathbb{F}_q)$ is not tight. In a loosely structured, last chapter of this thesis we collect further smaller observations related to expansion. We point out a link between discrete Morse theory and a technique for showing coboundary expansion, elaborate a bit on the hardness of computing coboundary expansion constants, propose a new criterion for coboundary expansion (in a very dense setting) and give one way of making the folklore result that expansion of links is a necessary condition for a simplicial complex to be an expander precise.
Publishing Year
Date Published
2022-08-11
Page
170
ISSN
IST-REx-ID

### Cite this

Wild P. High-dimensional expansion and crossing numbers of simplicial complexes. 2022. doi:10.15479/at:ista:11777
Wild, P. (2022). High-dimensional expansion and crossing numbers of simplicial complexes. Institute of Science and Technology (ISTA). https://doi.org/10.15479/at:ista:11777
Wild, Pascal. “High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes.” Institute of Science and Technology (ISTA), 2022. https://doi.org/10.15479/at:ista:11777.
P. Wild, “High-dimensional expansion and crossing numbers of simplicial complexes,” Institute of Science and Technology (ISTA), 2022.
Wild P. 2022. High-dimensional expansion and crossing numbers of simplicial complexes. Institute of Science and Technology (ISTA).
Wild, Pascal. High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes. Institute of Science and Technology (ISTA), 2022, doi:10.15479/at:ista:11777.
All files available under the following license(s):
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Title
High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes
Access Level
Open Access
2022-08-11
MD5 Checksum
4e96575b10cbe4e0d0db2045b2847774

Supplementary Material
File Name
flags.py 16.83 KB
Description
Code for computer-assisted proofs in Section 8.4.7 in Thesis
Access Level
Open Access
2022-08-10
MD5 Checksum
Supplementary Material
File Name
Description
Code for proof of Lemma 8.20 in Thesis
Access Level
Open Access
2022-08-10
MD5 Checksum
1f7c12dfe3bdaa9b147e4fbc3d34e3d5
Supplementary Material
File Name
Description
Code for proof of Proposition 7.9 in Thesis
Access Level
Open Access
2022-08-10
MD5 Checksum
4cf81455c49e5dec3b9b2e3980137eeb
Source File
File Name
Access Level
Closed Access