Kahn–Kalai large-subcube conjecture for monotone cube sets

Let A{0,1}nA\subset\{0,1\}^n be monotone increasing, with measure p=A/2n1/2p=|A|/2^n\leq 1/2, and let A\partial A denote its edge-boundary. A subcube is obtained by fixing coordinates; its codimension is the number of fixed coordinates.

Kahn–Kalai conjecture. For every L>0L>0, there exist L>0L'>0 and δ>0\delta>0 such that if

ALAlog2(2n/A),|\partial A|\leq L|A|\log_2(2^n/|A|),

then there is a subcube C{0,1}nC\subset\{0,1\}^n of codimension at most Llog2(1/p)L'\log_2(1/p), with all fixed coordinates equal to 11, satisfying

ACC(1+δ)p.\frac{|A\cap C|}{|C|}\geq(1+\delta)p.

The conjecture predicts that a monotone set with boundary within a constant factor of optimal must have increased density on a relatively low-codimension upper subcube. The source leaves it open and proposes a non-monotone extension.

Sources & referencesView supporting material

Primary source

David Ellis, “Almost isoperimetric subsets of the discrete cube”, arXiv:1310.8179 (2013).

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.