๐ฎ
๐ฎ
The Ethereal
An Improved Trickle-Down Theorem for Partite Complexes
August 09, 2022 ยท The Ethereal ยท ๐ Cybersecurity and Cyberforensics Conference
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Dorna Abdolazimi, Shayan Oveis Gharan
arXiv ID
2208.04486
Category
cs.DM: Discrete Mathematics
Cross-listed
cs.DS,
math.CO
Citations
5
Venue
Cybersecurity and Cyberforensics Conference
Last Checked
2 months ago
Abstract
We prove a strengthening of the trickle down theorem for partite complexes. Given a $(d+1)$-partite $d$-dimensional simplicial complex, we show that if "on average" the links of faces of co-dimension 2 are $\frac{1-ฮด}{d}$-(one-sided) spectral expanders, then the link of any face of co-dimension $k$ is an $O(\frac{1-ฮด}{kฮด})$-(one-sided) spectral expander, for all $3\leq k\leq d+1$. For an application, using our theorem as a black-box, we show that links of faces of co-dimension $k$ in recent constructions of bounded degree high dimensional expanders have spectral expansion at most $O(1/k)$ fraction of the spectral expansion of the links of the worst faces of co-dimension $2$.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Discrete Mathematics
๐ฎ
๐ฎ
The Ethereal
An Introduction to Temporal Graphs: An Algorithmic Perspective
๐ฎ
๐ฎ
The Ethereal
Guarantees for Greedy Maximization of Non-submodular Functions with Applications
๐ฎ
๐ฎ
The Ethereal
A note on the triangle inequality for the Jaccard distance
๐ฎ
๐ฎ
The Ethereal
Fast clique minor generation in Chimera qubit connectivity graphs
๐ฎ
๐ฎ
The Ethereal