5
$\begingroup$

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}$.

$\endgroup$
  • 1
    $\begingroup$ Just a remark: you can ask the same question for $0 < p \leq 2$. Then as $p$ tends to zero the problem degenerates into the vertex-isopermetric inequality, whose minimizers are Hamming balls instead of half-cubes. One can check that half-cubes become better than Hamming balls when $p>p_0(n)$ with $p_0(n)<1$ and $\lim p_0(n)=1$. It is possible that $C(p)=1$ for all $p \geq 1$ ? $\endgroup$ – Guillaume Aubrun May 17 '17 at 8:36
  • 1
    $\begingroup$ @AnthonyQuas Note that raising power is $p/2$ (and not $p$) $\endgroup$ – Guillaume Aubrun May 17 '17 at 14:12
  • $\begingroup$ @GuillaumeAubrun: thanks - I removed my comment $\endgroup$ – Anthony Quas May 17 '17 at 14:55
  • $\begingroup$ @GuillaumeAubrun I am not sure about $C(p)=1$ for $p\geq 1$. For $1<p\leq 2$ I can show that $C(p)\geq Z_{p/(p-1)}^{p}$ where $Z_{q}$ is the smallest positive zero of the confluent hypergeometric function $M(-q/2, 1/2, x^{2}/2)$. $\endgroup$ – Paata Ivanishvili May 17 '17 at 20:05
  • 1
    $\begingroup$ For certain values of $n$ and $p<1$ you can beat both the Hamming ball and the half-cube ; for example $n=5$, $p/2=0.43$, and $A$ the set of vertices with a majority of $1$ among the first 3 coordinates. It seems reasonable to conjecture that extremizers will always be obtained as the intersection of the discrete cube with a half-space in $\mathbb{R}^n$. $\endgroup$ – Guillaume Aubrun May 19 '17 at 8:45
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. By the way if $f$ is 0-1 indicator of a set $A \subseteq \{-1,1\}^{n}$ then $|\nabla \chi_{A}| = \frac{\sqrt{w_{A}(x)}}{2}$ and Bobkov's inequality gives $C(1)\geq \sqrt{\frac{2}{\pi}}\approx 0.79$. But Hamming balls give $C(1)\leq \frac{2}{\sqrt{\pi}}$ which is worse than $C(1)\leq 1$. So the optimizer cannot be Hamming ball in this particular case $\endgroup$ – Paata Ivanishvili May 19 '17 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.