Threshold for monotone symmetric properties through a logarithmic Sobolev inequality
成果类型：
Article
署名作者：
Rossignol, Raphael
署名单位：
Universite Paris Cite
刊物名称：
ANNALS OF PROBABILITY
ISSN/ISSBN：
0091-1798
DOI：
10.1214/009117906000000287
发表日期：
2006
页码：
1707-1725
关键词：
摘要：
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-know n logarithmic Sobolev inequality on {0, 1}(n). This new bound is shown to be asymptotically optimal.