On a biased edge isoperimetric inequality for the discrete cube

Abstract

The `full' edge isoperimetric inequality for the discrete cube (due to Harper, Bernstein, Lindsay and Hart) specifies the minimum size of the edge boundary $\partial A$ of a set $A\subset \{0,1{\}}^n$, as a function of $|A|$. A weaker (but more widely-used) lower bound is $|\partial A|\ge |A|{\log }_2(2^n/|A|)$, where equality holds iff $A$ is a subcube. In 2011, the first author obtained a sharp `stability' version of the latter result, proving that if $|\partial A|\le |A|(\log (2^n/|A|)+\epsilon )$, then there exists a subcube $C$ such that $|A\Delta C|/|A|=O(\epsilon /\log (1/\epsilon ))$. The `weak' version of the edge isoperimetric inequality has the following well-known generalization for the `$p$-biased' measure ${\mu }_p$ on the discrete cube: if $p\le 1/2$, or if $0<p<1$ and $A$ is monotone increasing, then $p{\mu }_p(\partial A)\ge {\mu }_p(A){\log }_p({\mu }_p(A))$. In this paper, we prove a sharp stability version of the latter result, which generalizes the aforementioned result of the first author. Namely, we prove that if $p{\mu }_p(\partial A)\le {\mu }_p(A)({\log }_p({\mu }_p(A))+\epsilon )$, then there exists a subcube $C$ such that ${\mu }_p(A\Delta C)/{\mu }_p(A)=O({\epsilon }^{\prime }/\log (1/{\epsilon }^{\prime }))$, where ${\epsilon }^{\prime }=\epsilon \ln (1/p)$. This result is a central component in recent work of the authors proving sharp stability versions of a number of Erdős-Ko-Rado type theorems in extremal combinatorics, including the seminal `complete intersection theorem' of Ahlswede and Khachatrian. In addition, we prove a biased-measure analogue of the `full' edge isoperimetric inequality, for monotone increasing sets, and we observe that such an analogue does not hold for arbitrary sets, hence answering a question of Kalai. We use this result to give a new proof of the `full' edge isoperimetric inequality, one relying on the Kruskal-Katona theorem.

36 pages. More explanations added, and minor corrections made, in response to referee comments