




























Abstract:We study the spectral gap of subgraphs of the hypercube induced by monotone subsets of vertices. For a monotone subset $A\subseteq\{0,1\}^{n}$ of density $\mu(A)$, the previous best lower bound on the spectral gap, due to Cohen, was $\gamma\gtrsim \mu(A)/n^{2}$, improving upon the earlier bound $\gamma\gtrsim \mu(A)^{2}/n^{2}$ established by Ding and Mossel. In this paper, we prove the optimal lower bound $\gamma\gtrsim \mu(A)/n$. As a corollary, we improve the mixing time upper bound of the random walk on constant-density monotone sets from $O(n^{3})$, as shown by Ding and Mossel, to $O(n^{2})$. Along the way, we develop two new inequalities that may be of independent interest: (1)~a directed $L^{2}$-Poincaré inequality on the hypercube, and (2)~an ``approximate'' FKG inequality for monotone sets.
From: Yumou Fei [view email]
[v1]
Mon, 5 May 2025 14:33:17 UTC (51 KB)
[v2]
Fri, 3 Jul 2026 18:12:11 UTC (40 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。