$L^{p}$ isoperimetric inequalities on the Hamming cube

Question

Let $A \subset \{-1,1\}^{n}$ be a subset of the Hamming cube with cardinality $|A|=2^{n-1}$. Define $w_{A} : \{-1,1\}^{n} \to \mathbb{N}\cup \{0\}$ so that $w_{A}(x)$ to be number of boundary edges to $A$ containing $x$, i.e., $w_{A}(x)$ counts number of edges of $\{-1,1\}^{n}$ with endpoints in $A$ and in the complement of $A$ so that one of the endpoint is $x$. Clearly $w_{A}(x)=0$ if $x$ is in the "strict interior" of $A$, or in the "strict complement" of $A$, and it is nonzero if and only if $x$ is on the "boundary" of $A$. Notice that $w_{A}(x)$ can be nonzero for some $x \notin A$.

The classical edge–isoperimetric inequality on the Hamming cube of Harper implies that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}(x) \geq 1 $$ and the constant $1$ on the right hand side is sharp.

My question is what is known about the best possible $C(p)\geq 0$ such that $$ \frac{1}{2^{n}}\sum_{x \in \{-1,1\}^{n}}w_{A}^{p/2}(x) \geq C(p), \quad 1\leq p\leq 2 $$ for all sets $A \subset \{-1,1\}^{n}$ with cardinality $2^{n-1}$.

Answer 1

The bound $C(1) \geq \frac{1}{\sqrt{2 \pi}}$ follows from "Bobkov's Inequality" [Bob97], which says that for any $f : \{-1,1\}^n \to [0,1]$ it holds that $\mathcal{U}(\mathbb{E}[f]) \leq \mathbb{E}\sqrt{\mathcal{U}(f)^2 + |\nabla f|^2}$, where $\nabla f$ is the discrete gradient $\nabla f(x) = \left(\frac{f(x_1, \dots, x_{i-1}, 1, x_{i+1}, \dots, x_n) - f(x_1, \dots, x_{i-1}, -1, x_{i+1}, \dots, x_n)}{2}\right)_{i=1\dots n}$ and $\mathcal{U}$ denotes the "Gaussian isoperimetric function" $\phi \circ \overline{\Phi}^{-1}$ (with $\phi$ the Gaussian pdf and $\overline{\Phi}$ the Gaussian complementary cdf). In particular, if $f$ is the $0$-$1$ indicator of a set $A \subseteq \{-1,1\}^n$, then this reduces to $\mathbb{E}_x[\sqrt{w_A(x)}] \geq \mathcal{U}(\text{vol}(A))$, where $\text{vol}(A) = |A|/2^{n}$. Thus in your case where $\text{vol}(A) = 1/2$ we get a lower bound of $\mathcal{U}(1/2) = \frac{1}{\sqrt{2 \pi}}$.

This is sharp up to a factor of $\sqrt{2}$ by virtue of the "Majority" function -- i.e., $A$ being a Hamming ball of radius $n/2$ -- which has $\mathbb{E}_x[\sqrt{w_A(x)}] \sim \frac{1}{\sqrt{\pi}}$. Bobkov remarks on this missing factor of $\sqrt{2}$; presumably $\frac{1}{\sqrt{\pi}}$ is the correct answer but it's not known how to improve $\frac{1}{\sqrt{2\pi}}$ as far as I'm aware.

Given this result, one can get $C(p) \geq \left(\frac{1}{2\pi}\right)^{p/2}$ for any $1 < p < 2$ by monotonicity of $\ell_p$-norms, which is a decent bound but is surely not optimal. Getting the optimal answer in this range is presumably harder than getting the optimal answer for $p = 1$.

By the way, it was Talagrand who first studied the $p = 1$ case; this notion of looking at the average square-root of the number of sensitive coordinates seems to be a pretty good notion of "discrete surface area". Talagrand's original paper [Tal93] proved Bobkov's Inequality (for sets $A$) up to a universal constant factor on the LHS; in particular, he established $C(1)$ is bounded away from $0$ by a univeral constant.

[Bob97] Bobkov, S.G., An isoperimetric inequality on the discrete cube and an elementary proof of the isoperimetric inequality in Gauss space, Ann. Probab. 25, No.1, 206-214 (1997). ZBL0883.60031.

[Tal93] Talagrand, M., Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem, Geom. Funct. Anal. 3, No.3, 295-314 (1993). ZBL0806.46035.

Answer 2

We just posted a preprint on arXiv with David Beltran and Jose Madrid, where in Corollary 1.7 it is proved that $$ C(p)=1 \quad \text{for all} \quad p \geq 1.06 $$ partially answering the question. Using the techniques from the paper one could push $1.06$ up to $p_{0} =1.0598....$ which is the smallest positive number such that the polynomial $$ P(y) = (11-\frac{70}{9}\cdot 2^{1/2})2^{7}y^{6}+(2^{1/2+7}-181)\frac{2^{6}}{3}y^{5}+(1453-\frac{3082}{2}\cdot 2^{1/2})\frac{2^{3}}{3}y^{4}-(\frac{331}{3}-78\cdot2^{1/2})2^{4}y^{3}+(563-\frac{1192}{3}\cdot 2^{1/2})\frac{2}{3}y^{2}-(47-2^{1/2+5})\frac{2}{3}y+2^{p/2}-1 $$ of degree 6 is nonnegative on $[0,1]$.

So it looks like (as Guillaume Aubrun pointed out in the comment) we should have $C(p)=1$ for all $p\geq 1$. The lower bound $C(1)\geq \sqrt{\frac{2}{\pi}}=0.79...$ coming from Bobkov's inequality that Ryan mentioned turns out not to be sharp. There is another nice paper of Bobkov--Gotze which implies $C(1)\geq \frac{\sqrt{3}}{2}=0.86...$. This bound is also not sharp, in the paper we show $C(1)\geq \sqrt{2^{3/2}-2}=0.91...$.