Submit progress

on Critical exponent for isoperimetric inequality on the Hamming cube ($C_{11b}$)

The statement

Let $Q_{n} =$ {-1,1}^n be the Hamming cube (two vertices are adjacent if they differ in exactly one coordinate). For a set $A \subset Q_{n}$ define the function $h_{A}:Q_{n}\to$ {0,1,...,n} by

$h_{A}(x)=0$ if $x\notin A$ ;
if $x\in A$ , then $h_{A}(x)$ is the number of neighbors of $x$ that lie in the complement $A^c$ .

Let $x$ be uniformly distributed on $Q_{n}$ , and write $\mathbb{E}$ for expectation. Then $C_{11b}$ is the infimum of all exponents $\beta>0$ such that for every $n\ge 1$ and every set $A\subset Q_n$ of cardinality $2^{n-1}$ one has

\mathbb{E} (h_{A}(x))^\beta \ \ge \frac{1}{2}.

(For a codimension-1 subcube $A$ one has $h_{A}(x)=1$ on $A$ and $0$ on $A^c$ , so the left-hand side equals $1/2$ for every $\beta>0$ .)

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.