The critical exponent for isoperimetric inequality on the hamming cube
Description of constant
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$.)
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $1$ | Classical (e.g. [Har1966]) | Follows from the edge isoperimetric inequality; equality for a codimension-1 subcube |
| $\log_2(3/2)\approx 0.58496$ | [KP2020] | In particular implies $\mathbb{E}h_{A}^\beta \ge 1/2$ for all half-size $A$ |
| $0.53$ | [BIM2023] | Sharp inequality of the form $\mathbb{E}h_{A}^{0.53}\ge 2\mu(A)(1-\mu(A))$ for $\mu(A)\ge 1/2$; gives the half-size case |
| $0.50057$ | [DIR2024] | Current best published; Theorem 1.1 implies the half-size case |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $0.5$ | [BIM2023] | For every $\beta<1/2$, Hamming ball examples give half-size sets with $\mathbb{E}h_{A}(x)^\beta$ arbitrarily small as $n\to\infty$ |
Additional comments and links
- Conjecturally $C_{11b}=1/2$ (this is the $k=1$ case of the “subcubes are extremizers” conjecture in [DIR2024]).
-
At the critical exponent $\beta=0.5$, [DIR2024, Thm. 1.4] gives the near-sharp estimate
$\mathbb{E} (h_{A}(x))^{1/2} \ge 0.4985$ for any $n\geq 1$ and any set $A \subset Q_{n}$ of cardinality $2^{n-1}$
so the conjectured half-size inequality at $\beta=0.5$ is known up to about $1.5\times 10^{-3}$ in the moment value arXiv:2407.12674
- Connection to the Kahn–Park conjecture (cube separation). Kahn and Park [KP2020] conjectured that there exists an absolute constant $K>0$ such that for every partition $(A,B,W)$ of the $n$-dimensional Hamming cube with $\mu(A)=1/2$ (here $\mu$ is the uniform probability measure) we have
where $|\nabla(A,B)|$ denotes the normalized number of edges with one endpoint in $A$ and the other in $B$ (i.e. $2^{-n}$ times the number of such edges). Any admissible exponent $\beta$ in the definition of $C_{11b}$ implies the weaker bound with $n^{0.5}$ replaced by $n^{\beta}$. Thus, improving the upper bound on $C_{11b}$ gives partial progress towards the Kahn–Park conjecture; if $C_{11b}=0.5$, then the conjecture would follow (in fact with $K=1$).
References
- [BIM2023] Beltran, D.; Ivanisvili, P.; Madrid, J. On sharp isoperimetric inequalities on the hypercube. arXiv:2303.06738 (2023).
- [DIR2024] Durcik, P.; Ivanisvili, P.; Roos, J. Sharp isoperimetric inequalities on the Hamming cube near the critical exponent. arXiv:2407.12674 (2024).
- [Har1966] Harper, L. Optimal numberings and isoperimetric problems on graphs. J. Comb. Theory 1 (1966), no. 3, 385–393.
- [KP2020] Kahn, J.; Park, J. An isoperimetric inequality for the Hamming cube and some consequences. Proc. Amer. Math. Soc. 148 (2020), 4213–4224. arXiv:1909.04274