The fixed-error hybrid isoperimetric conjecture for the Hamming cube

Let QnQ_n be the nn-dimensional Hamming cube with vertex set VV, and let (A,B,W)(A,B,W) be a partition of VV. Write abla(A,B)={(x,y):xA,yB} abla(A,B)=\{(x,y):x\in A,y\in B\} for the edges between AA and BB, and let μ(A)=A/2n\mu(A)=|A|/2^n.

Fixed-error hybrid isoperimetric conjecture. There is a fixed constant KK such that, whenever μ(A)=1/2\mu(A)=1/2,

(A,B)+KnW2n1.|\nabla(A,B)|+K\sqrt{n}\,|W|\geq 2^{n-1}.

This is a proposed hybrid form of the edge-isoperimetric inequality, quantifying how a small exceptional part WW affects separation of two parts of the cube. The source gives no resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Jeff Kahn and Jinyoung Park, “An isoperimetric inequality for the Hamming cube and some consequences”, arXiv:1909.04274 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.