The fixed-error hybrid isoperimetric conjecture for the Hamming cube

About 7 years old · traced to

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):x∈A,y∈B} 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)∣+Kn ∣W∣≥2n−1.|\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.

References

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.