The maximal 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. For a=Aa=|A|, define

(a)=min{A:A=a},\partial(a)=\min\{|\partial A|:|A|=a\},

and let (a)\nabla(a) be defined analogously using the edge boundary. Write (A,B)={(x,y):xA,yB}\nabla(A,B)=\{(x,y):x\in A,y\in B\}.

Maximal hybrid isoperimetric conjecture. If A=a|A|=a, then

(A,B)(a)+W(a)1.\frac{|\nabla(A,B)|}{\nabla(a)}+\frac{|W|}{\partial(a)}\geq 1.

This conjecture would give a general tradeoff between the edges joining AA to BB and the exceptional set WW, extending the usual vertex- and edge-isoperimetric bounds. 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.