An Improved Trickle-Down Theorem for Partite Complexes
An Improved Trickle-Down Theorem for Partite Complexes
复制标题
改进的分配合物滴流定理
DOI：
10.48550/arxiv.2208.04486
复制
发表时间：
2022
影响因子：
2
通讯作者：
S. Gharan
中科院分区：
文献类型：
--
作者：
Dorna Abdolazimi;S. Gharan
我们证明了分部复合体滴流定理的强化。给定 $(d+1)$ 分 $d$ 维单纯复形，我们证明，如果“平均”，同维 2 的面的链接是 $\frac{1-\delta}{d}$-(单边) 谱扩展器，那么同维 $k$ 的任何面的链接都是 $O(\frac{1-\delta}{k\delta})$-(单边) 谱扩展器，对于所有 $3\leq k\leq d+1$。对于一个应用程序，使用我们的定理作为黑盒，我们表明在最近有界度高维扩展器的构造中，共维度 $k$ 的面的链接的谱扩展最多为共维度 $2$ 最差面的链接的谱扩展的 $O(1/k)$ 部分。
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-\delta}{d}$-(one-sided) spectral expanders, then the link of any face of co-dimension $k$ is an $O(\frac{1-\delta}{k\delta})$-(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$.
DOI：
10.1109/focs52979.2021.00024
发表时间：
2021-06
期刊：
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Dorna Abdolazimi;Kuikui Liu;S. Gharan
通讯作者：
Dorna Abdolazimi;Kuikui Liu;S. Gharan
DOI：
10.1145/3406325.3451035
发表时间：
2020-11
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Zongchen Chen;Kuikui Liu;Eric Vigoda
通讯作者：
Zongchen Chen;Kuikui Liu;Eric Vigoda
DOI：
10.1109/focs.2019.00021
发表时间：
2019
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Alev, Vedat Levi;Granha Jeronimo, Fernando;Tulsiani, Madhur
通讯作者：
Tulsiani, Madhur