TOPICS
Search

Friedgut-Kalai Sharp-Threshold Conjecture

The Friedgut-Kalai sharp-threshold conjecture predicts a universal upper bound of order (lnn)^(-2) on the transition width of a nontrivial increasing graph property on n vertices, for fixed endpoint probabilities (Friedgut and Kalai 1996, Conjecture 1.2). For such a graph property P, let mu_p(P) be the probability that the random graph G(n,p) belongs to P, and define

p_a(P)=inf{p in [0,1]:mu_p(P)>=a}

for 0<a<1. The transition width is p_(1-epsilon)(P)-p_epsilon(P), where 0<epsilon<1/2. It measures an absolute change in the edge probability p.

Friedgut and Kalai (1996) proved an upper bound with denominator lnn and made the conjecture that it could be replaced by (lnn)^2 with the same dependence on epsilon. For example, the graph property of containing a clique of order proportional to lnn can have transition width of order (lnn)^(-2) (Friedgut and Kalai 1996, p. 2994).

Friedgut and Kalai (1996, §5) also proposed the corresponding exponent r/(r-1) for r-uniform hypergraphs. Here a hypergraph property is a Boolean function of the possible hyperedges that is invariant under every permutation of the vertices. Using independent hyperedges of probability p defines mu_p and p_a in the same way.

See also

Average Sensitivity, Graph Property, Hypergraph, Random Graph

Explore with Wolfram|Alpha

References

Friedgut, E. and Kalai, G. "Every Monotone Graph Property Has a Sharp Threshold." Proc. Amer. Math. Soc. 124, 2993-3002, 1996. https://doi.org/10.1090/S0002-9939-96-03732-X.

Cite this as:

Weisstein, Eric W. "Friedgut-Kalai Sharp-Threshold Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Friedgut-KalaiSharp-ThresholdConjecture.html

Subject classifications