For an integer , a graph property is a family of simple graphs on vertices invariant under vertex permutations. It is increasing if adding edges preserves membership. It is nontrivial if it is neither empty nor the whole space. Write for its probability when edges are present independently with probability . For , define . The sharp-threshold question asks for a uniform upper bound on the transition width for . For a Boolean function of the edges, its total pivotal influence is the sum over edges of the probabilities that flipping that edge changes under the same product law. Write for its variance under this law. All logarithms are natural.
Friedgut and Kalai proved the width bound for every nontrivial increasing graph property, with an absolute constant . They conjectured the denominator with the same dependence on . Bourgain and Kalai obtained the bound for each fixed and , with independent of .
The preprint proves that every nontrivial increasing graph property satisfies . For every Boolean graph function invariant under vertex permutations and every , the preprint proves , without a monotonicity assumption.
The Lean library SharpThreshold contains both estimates with these constants. Lean has checked every result of the Lean library, so the Lean library is the reference for the statements on these pages. Each result is stated as in the Lean library and linked to the declaration behind it, with the preprint’s statement given beside any differing statement. The preprint is a guide only, giving the results their order and names.
SharpThreshold is a Lean library: 16 items, in four groups. Each has a page written by OctoInform, listed below.
No item matches.