2026-10-08T18:23:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24408 2025-12-12T14:01:34Z ddc:004 open_access

On the Spectral Expansion of Monotone Subsets of the Hypercube Fei, Yumou Ferreira Pinto Jr., Renato Random walks mixing time FKG inequality Poincaré inequality directed isoperimetry We study the spectral gap of subgraphs of the hypercube induced by monotone subsets of vertices. For a monotone subset A ⊆ {0,1}ⁿ of density μ(A), the previous best lower bound on the spectral gap, due to Cohen [Cohen, 2016], was γ ≳ μ(A)/n², improving upon the earlier bound γ ≳ μ(A)²/n² established by Ding and Mossel [Ding and Mossel, 2014]. In this paper, we prove the optimal lower bound γ ≳ μ(A)/n. As a corollary, we improve the mixing time upper bound of the random walk on constant-density monotone sets from O(n³), as shown by Ding and Mossel, to O(n²). Along the way, we develop two new inequalities that may be of independent interest: (1) a directed L²-Poincaré inequality on the hypercube, and (2) an "approximate" FKG inequality for monotone sets. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yumou Fei and Renato Ferreira Pinto Jr. 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.42 urn:nbn:de:0030-drops-244081 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.42 eng https://creativecommons.org/licenses/by/4.0/legalcode