OctoInformBeta

Uniform influence and sharp thresholds for graph and hypergraph properties

For an integer n≥2n\ge2, a graph property 𝒫\mathcal P is a family of simple graphs on nn 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 μp(𝒫)\mu_p(\mathcal P) for its probability when edges are present independently with probability p∈[0,1]p\in[0,1]. For 0<a<10<a<1, define pa(𝒫)=inf⁡{p∈[0,1]:μp(𝒫)≥a}p_a(\mathcal P)=\inf\{p\in[0,1]:\mu_p(\mathcal P)\ge a\}. The sharp-threshold question asks for a uniform upper bound on the transition width p1−ε(𝒫)−pε(𝒫)p_{1-\varepsilon}(\mathcal P)-p_\varepsilon(\mathcal P) for 0<ε<1/20<\varepsilon<1/2. For a Boolean function ff of the edges, its total pivotal influence Ip(f)I_p(f) is the sum over edges of the probabilities that flipping that edge changes ff under the same product law. Write Var⁡p(f)\operatorname{Var}_p(f) for its variance under this law. All logarithms are natural.

Friedgut and Kalai proved the width bound Clog⁡(1/(2ε))/log⁡nC\log(1/(2\varepsilon))/\log n for every nontrivial increasing graph property, with an absolute constant CC. They conjectured the denominator (log⁡n)2(\log n)^2 with the same dependence on ε\varepsilon. Bourgain and Kalai obtained the bound Cη,ε(log⁡n)−2+ηC_{\eta,\varepsilon}(\log n)^{-2+\eta} for each fixed η>0\eta>0 and 0<ε<1/20<\varepsilon<1/2, with Cη,εC_{\eta,\varepsilon} independent of nn.

The preprint proves that every nontrivial increasing graph property satisfies p1−ε(𝒫)−pε(𝒫)≤219log⁡(1/(2ε))/(log⁡n)2p_{1-\varepsilon}(\mathcal P)-p_\varepsilon(\mathcal P)\le 2^{19}\log(1/(2\varepsilon))/(\log n)^2. For every Boolean graph function ff invariant under vertex permutations and every 0<p<10<p<1, the preprint proves Var⁡p(f)≤217Ip(f)/(log⁡n)2\operatorname{Var}_p(f)\le 2^{17}I_p(f)/(\log n)^2, 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.

The Lean library: SharpThreshold

SharpThreshold is a Lean library: 16 items, in four groups. Each has a page written by OctoInform, listed below.