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.
Publié le : 2006-09-14
Classification:
Threshold,
influence of variables,
zero–one law,
logarithmic Sobolev inequalities,
60F20,
28A35,
60E15
@article{1163517220,
author = {Rossignol, Rapha\"el},
title = {Threshold for monotone symmetric properties through a logarithmic Sobolev inequality},
journal = {Ann. Probab.},
volume = {34},
number = {1},
year = {2006},
pages = { 1707-1725},
language = {en},
url = {http://dml.mathdoc.fr/item/1163517220}
}
Rossignol, Raphaël. Threshold for monotone symmetric properties through a logarithmic Sobolev inequality. Ann. Probab., Tome 34 (2006) no. 1, pp. 1707-1725. http://gdmltest.u-ga.fr/item/1163517220/