OpenFrontiers
Join
← Back to the index
OP-12012SolvedCombinatorics

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

Critical exponent for isoperimetric inequality on the Hamming cube: determine C11bC_{11b} or improve its bounds; the repository records 0.5 (lower) and 0.5 (upper).

MSC 60E15 · Inequalities; stochastic orderingsMSC 06E30 · Boolean functions

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

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

  • hA(x)=0h_{A}(x)=0 if x∉Ax\notin A;
  • if x∈Ax\in A, then hA(x)h_{A}(x) is the number of neighbors of xx that lie in the complement AcA^c.

Let xx be uniformly distributed on QnQ_{n}, and write E\mathbb{E} for expectation. Then C11bC_{11b} is the infimum of all exponents β>0\beta>0 such that for every n≥1n\ge 1 and every set A⊂QnA\subset Q_n of cardinality 2n−12^{n-1} one has

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

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

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

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

E(hA(x))1/2≥0.4985\mathbb{E} (h_{A}(x))^{1/2} \ge 0.4985 for any n≥1n\geq 1 and any set A⊂QnA \subset Q_{n} of cardinality 2n−12^{n-1}

so the conjectured half-size inequality at β=0.5\beta=0.5 is known up to about 1.5×10−31.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>0K>0 such that for every partition (A,B,W)(A,B,W) of the nn-dimensional Hamming cube with μ(A)=1/2\mu(A)=1/2 (here μ\mu is the uniform probability measure) we have
∣∇(A,B)∣+Kn0.5 μ(W)≥12,|\nabla(A,B)| + Kn^{0.5}\ \mu(W) \ge \frac12,

where ∣∇(A,B)∣|\nabla(A,B)| denotes the normalized number of edges with one endpoint in AA and the other in BB (i.e. 2−n2^{-n} times the number of such edges). Any admissible exponent β\beta in the definition of C11bC_{11b} implies the weaker bound with n0.5n^{0.5} replaced by nβn^{\beta}. Thus, improving the upper bound on C11bC_{11b} gives partial progress towards the Kahn--Park conjecture; if C11b=0.5C_{11b}=0.5, then the conjecture would follow (in fact with K=1K=1).

References (from the repository page)

  • [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

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 0.5; best known upper bound 0.5. Values marked with an asterisk have minimal verification. The recorded bounds coincide, so the repository treats the value as determined.

Known upper bounds

Bound Reference Comments
11 Classical (e.g. [Har1966]) Follows from the edge isoperimetric inequality; equality for a codimension-1 subcube
log⁡2(3/2)≈0.58496\log_2(3/2)\approx 0.58496 [KP2020] In particular implies EhAβ≥1/2\mathbb{E}h_{A}^\beta \ge 1/2 for all half-size AA
0.530.53 [BIM2023] Sharp inequality of the form EhA0.53≥2μ(A)(1−μ(A))\mathbb{E}h_{A}^{0.53}\ge 2\mu(A)(1-\mu(A)) for μ(A)≥1/2\mu(A)\ge 1/2; gives the half-size case
0.500570.50057 [DIR2024] Current best published; Theorem 1.1 implies the half-size case
0.50.5 [DIRX2026] Solves the problem by establishing β=0.5\beta=0.5.

Known lower bounds

Bound Reference Comments
0.50.5 [BIM2023] For every β<1/2\beta<1/2, Hamming ball examples give half-size sets with EhA(x)β\mathbb{E}h_{A}(x)^\beta arbitrarily small as n→∞n\to\infty
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Critical exponent for isoperimetric inequality on the Hamming cube ($C_{11b}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.