Kahn and Kalai's dense-subcube conjecture

Let A{0,1}nA\subset\{0,1\}^n be monotone increasing, with measure α=A/2n1/2\alpha=|A|/2^n\leq 1/2. Its edge-boundary is denoted by A\partial A. Kahn and Kalai's 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 measure at least αL\alpha^{L'}, with all fixed coordinates equal to 11, such that

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

The hypothesis requires the boundary to be within a constant factor of the edge-isoperimetric minimum, while the conclusion finds a fairly large subcube on which the density increases by a constant factor. The source gives no resolution.

Sources & referencesView supporting material

Primary source

Itai Benjamini, David Ellis, Ehud Friedgut, Nathan Keller and Arnab Sen, “Juntas in the ^1-grid and Lipschitz maps between discrete tori”, arXiv:1311.6958 (2015).

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.