Kahn–Kalai optimal-scale conjecture

About 20 years old · traced to

Let XX be a finite set of size nn, let F⊆2X{\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

p m′(p)≤Cm(p)log⁡pm(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)log⁡n,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.

References

Primary source

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

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.