On the Spectral Expansion of Monotone Subsets of the Hypercube

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.

minor modifications in the second version