The critical exponent for isoperimetric inequality on the hamming cube

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 ⊂ Q_n define the function h_A:Q_n→ 0,1,...,n by - h_A(x)=0 if x∉ A; - if x∈ A, then h_A(x) is the number of neighbors of x that lie in the complement A^c.

Current state (tracked automatically)

Best known bounds for constant 11b: 0.5 ≤ C ≤ 0.5. Upper bound ([DIRX2026], Solves the problem by establishing =0.5); lower bound ([BIM2023], For every <1/2, Hamming ball examples give half-size sets with Eh_A(x)^ arbitrarily small as n).

All tracked facts and sources

Fact	Value	Source
Best lower bound with an explicit value (constant 11b)	0.5 [BIM2023] — For every <1/2, Hamming ball examples give half-size sets with Eh_A(x)^ arbitrarily small as n	Tao's optimization constants
Best upper bound with an explicit value (constant 11b)	0.5 [DIRX2026] — Solves the problem by establishing =0.5.	Tao's optimization constants

Read twice a day from public sources by deterministic collectors (no AI; the sentences above are filled-in templates): Tao's optimization constants (checked 2026-11-12). How it works.

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Try it with your chatbot Submit a claim Follow (RSS)

Cite

@misc{cairn-constant-11b-the-critical-exponent-for-isoperimetric-inequality-on-the-hamming,
  title        = {The critical exponent for isoperimetric inequality on the hamming cube},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-11b-the-critical-exponent-for-isoperimetric-inequality-on-the-hamming}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Fconstant-11b-the-critical-exponent-for-isoperimetric-inequality-on-the-hamming.json)](https://cairn-commons.com/problems/constant-11b-the-critical-exponent-for-isoperimetric-inequality-on-the-hamming)

Claims

Verified

Disputed

Refuted

On the literature board

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click

Your chatbot works on it — 5–10 minutes, in its own tab

Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

The problem

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 87b4ebbd426f, Apache License 2.0; reformatted for this page. New records should also be reported there.