2025/05/05 by Fei, Yumou, Pinto, Renato Ferreira · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2505.02685
We study the spectral gap of subgraphs of the hypercube induced by monotone subsets of vertices. For a monotone subset A⊆\0,1\n of density μ(A), the previous best lower bound on the spectral gap, due to Cohen, was γ\gtrsim μ(A)/n2, improving upon the earlier bound γ\gtrsim μ(A)2/n2 established by Ding and Mossel. In this paper, we prove the optimal lower bound γ\gtrsim μ(A)/n. As a corollary, we improve the mixing time upper bound of the random walk on constant-density monotone sets from O(n3), as shown by Ding and Mossel, to O(n2). Along the way, we develop two new inequalities that may be of independent interest: (1)~a directed L2-Poincaré inequality on the hypercube, and (2)~an ``approximate'' FKG inequality for monotone sets.