Friedgut–Kalai sharp-threshold conjecture for monotone graph properties

Let PP be a monotone property of graphs on nn vertices, let upn u_p^n denote the product measure on graphs in which each edge is present with probability pp, and let uqn u_q^n be defined similarly. For epsilon>0epsilon>0, assume

q=p+clog(1/2ϵ)log2n.q=p+c\frac{\log(1/2\epsilon)}{\log^2 n}.

Friedgut–Kalai conjecture. There is an absolute constant cc such that, if upn(P)>ϵ u_p^n(P)>\epsilon, then

νqn(P)>1ϵ.\nu_q^n(P)>1-\epsilon.

This is a proposed improvement of the Friedgut–Kalai sharp-threshold bound, replacing the denominator logn\log n by log2n\log^2 n for arbitrary monotone graph properties. The supplied source does not state whether the question has been resolved.

Sources & referencesView supporting material

Primary source

Kevin Tanguy, “Talagrand inequality at second order and application to Boolean analysis”, arXiv:1801.08931 (2019).

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.