Kahn–Kalai large-subcube conjecture for monotone cube sets
Kahn–Kalai large-subcube conjecture for monotone cube sets
Let be monotone increasing, with measure , and let denote its edge-boundary. A subcube is obtained by fixing coordinates; its codimension is the number of fixed coordinates.
Kahn–Kalai conjecture. For every , there exist and such that if
then there is a subcube of codimension at most , with all fixed coordinates equal to , satisfying
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
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.