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 \in / 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 $E$ for expectation. Then $C_{11 b}$ is the infimum of all exponents $β > 0$ such that for every $n \geq 1$ and every set $A \subset Q_{n}$ of cardinality $2^{n - 1}$ one has

$E (h_{A} (x))^{β} \geq \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 $β > 0$ .)

Known upper bounds

Bound	Reference	Comments
$1$	Classical (e.g. [Har1966])	Follows from the edge isoperimetric inequality; equality for a codimension-1 subcube
$lo g_{2} (3/2) \approx 0.58496$	[KP2020]	In particular implies $E h_{A}^{β} \geq 1/2$ for all half-size $A$
$0.53$	[BIM2023]	Sharp inequality of the form $E h_{A}^{0.53} \geq 2 μ (A) (1 - μ (A))$ for $μ (A) \geq 1/2$ ; gives the half-size case
$0.50057$	[DIR2024]	Current best published; Theorem 1.1 implies the half-size case
$0.5$	[DIRX2026]	Solves the problem by establishing $β = 0.5$ .

Known lower bounds

Bound	Reference	Comments
$0.5$	[BIM2023]	For every $β < 1/2$ , Hamming ball examples give half-size sets with $E h_{A} (x)^{β}$ arbitrarily small as $n \to \infty$

Additional comments and links

Conjecturally $C_{11 b} = 1/2$ (this is the $k = 1$ case of the “subcubes are extremizers” conjecture in [DIR2024]).
At the critical exponent $β = 0.5$ , [DIR2024, Thm. 1.4] gives the near-sharp estimate

$E (h_{A} (x))^{1/2} \geq 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 $β = 0.5$ is known up to about $1.5 \times 1 0^{- 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 $μ (A) = 1/2$ (here $μ$ is the uniform probability measure) we have

$∣\nabla (A, B) ∣ + K n^{0.5} μ (W) \geq \frac{1}{2},$

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 $β$ in the definition of $C_{11 b}$ implies the weaker bound with $n^{0.5}$ replaced by $n^{β}$ . Thus, improving the upper bound on $C_{11 b}$ gives partial progress towards the Kahn--Park conjecture; if $C_{11 b} = 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).
[DIRX2026] Durcik, P.; Ivanisvili, P.; Roos, J; Xie, X. Sharp isoperimetric inequalities on the Hamming cube II: The critical exponent arXiv:2602.20462 (2026)
[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

What counts as progress

A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
A formal proof (Lean) of a known bound, or a precise error in a claimed one.
New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.