A Sharp Threshold Bound for Monotone Graph Properties
For every integer , every nontrivial increasing family of graphs on vertices invariant under all vertex permutations, and every , .
The proof in Section 4 is complete and elementary once Theorem 1.2 is established: on ensures unique quantiles, division by is valid on , and the inequality holds for .
“Theorem 1.1 (Friedgut–Kalai sharp-threshold conjecture). For every integer n >= 2, every nontrivial increasing family P of graphs on n vertices invariant under all vertex permutations, and every 0 < epsilon < 1/2, (P) - p_epsilon(P) <= 2^19 / (log n)^2 log(1 / (2 epsilon)).” · Show in paper