The sharp stability conjecture for the edge-isoperimetric inequality in the discrete cube

Let [n]={1,,n}[n]=\{1,\ldots,n\}, let P([n])\mathcal{P}([n]) denote the discrete cube, and let F\partial\mathcal{F} be the edge boundary of a family FP([n])\mathcal{F}\subset\mathcal{P}([n]). Let LP([n])\mathcal{L}\subset\mathcal{P}([n]) be the initial segment of the lexicographic ordering with L=F|\mathcal{L}|=|\mathcal{F}|. Two families are weakly isomorphic when one can be obtained from the other by a cube automorphism of the relevant type.

The sharp stability conjecture. If FP([n])\mathcal{F}\subset\mathcal{P}([n]) and LP([n])\mathcal{L}\subset\mathcal{P}([n]) is as above, then there exists a family GP([n])\mathcal{G}\subset\mathcal{P}([n]) weakly isomorphic to L\mathcal{L} such that

FΔG2(FL).|\mathcal{F}\mathbin{\Delta}\mathcal{G}|\leq 2\bigl(|\partial\mathcal{F}|-|\partial\mathcal{L}|\bigr).

The paper proves the same stability statement with an unspecified absolute constant in place of 22, and explains that the constant 22 is the conjectured sharp value. The conjecture remains open in the source.

Sources & referencesView supporting material

Primary source

David Ellis, Nathan Keller and Noam Lifshitz, “On the structure of subsets of the discrete cube with small edge boundary”, arXiv:1612.06680 (2018).

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.