Kahn and Kalai's dense-subcube conjecture

At least 12 years old · documented by

Let A⊂{0,1}nA\subset\{0,1\}^n be monotone increasing, with measure α=∣A∣/2n≤1/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

∣∂A∣≤L∣A∣log⁡2(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

∣A∩C∣∣C∣≥(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.

References

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.