Threshold for monotone symmetric properties through a logarithmic Sobolev inequality

Abstract

Threshold phenomena are investigated using a general approach, following Talagrand [Ann. Probab. 22 (1994) 1576--1587] and Friedgut and Kalai [Proc. Amer. Math. Soc. 12 (1999) 1017--1054]. The general upper bound for the threshold width of symmetric monotone properties is improved. This follows from a new lower bound on the maximal influence of a variable on a Boolean function. The method of proof is based on a well-known logarithmic Sobolev inequality on $\{0,1{\}}^n$. This new bound is shown to be asymptotically optimal.

Published at http://dx.doi.org/10.1214/009117906000000287 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• The Scaling Window of the 2-SAT Transition

Cited by in corpus (16)

• Sublinear variance in first-passage percolation for general distributions
• Approximate zero-one laws and sharpness of the percolation transition in a class of models including two-dimensional Ising percolation
• Cuts in Cartesian Products of Graphs
• Sublinearity of the travel-time variance for dependent first-passage percolation
• Sharp threshold for percolation on expanders
• Approximate zero-one laws and sharpness of the percolation transition in a class of models including 2D Ising percolation
• On codes decoding a constant fraction of errors on the BSC
• Four Talagrand inequalities under the same umbrella
• An unified approach to the Junta theorem for discrete and continuous models
• Almost isoperimetric subsets of the discrete cube
• Exponential concentration for First Passage Percolation through modified Poincare inequalities
• Edge-isoperimetric inequalities and influences
• Threshold phenomena on product spaces: BKKKL revisited (once more)
• Submean variance bound for effective resistance of random electric networks
• A stability result for the cube edge isoperimetric inequality
• Talagrand's influence inequality revisited