Skip to main content
4 of 4
formatting, added tags
YCor
  • 63.9k
  • 5
  • 187
  • 286

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

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

Paata Ivanishvili
  • 3.9k
  • 1
  • 21
  • 30