Kahn and Kalai's dense-subcube conjecture
Kahn and Kalai's dense-subcube conjecture
Let be monotone increasing, with measure . Its edge-boundary is denoted by . Kahn and Kalai's conjecture. For every , there exist and such that if
then there is a subcube of measure at least , with all fixed coordinates equal to , such that
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.