Kahn–Kalai optimal-scale conjecture

From papers

Let XX be a finite set of size nn, let F2X{\cal F}\subseteq2^X be monotone, and let pc(F)p_c({\cal F}) satisfy μpc(F)(F)=1/2\mu_{p_c({\cal F})}({\cal F})=1/2. Call F{\cal F} (C,p)(C,p)-optimal when

pm(p)Cm(p)logpm(p),m(p)=μp(F).p\,m'(p)\leq C m(p)\log_p m(p),\qquad m(p)=\mu_p({\cal F}).

Optimal-scale conjecture. For each C>0C>0 there is an ε>0\varepsilon>0 such that, for every monotone F{\cal F}, there exists

p[εpc(F)logn,pc(F)]p\in\left[\frac{\varepsilon p_c({\cal F})}{\log n},p_c({\cal F})\right]

for which F{\cal F} is (Clog(1/p),p)(C\log(1/p),p)-optimal. The paper says this conjecture, together with part (c) of its isoperimetric-structure conjecture, would imply the main expectation-threshold conjecture; it was not known whether the asserted scale exists.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Jeff Kahn and Gil Kalai, “Thresholds and expectation thresholds”, arXiv:math/0603218 (2006).

Solutions 0

No solutions have been posted yet.