Threshold for monotone symmetric properties through a logarithmic Sobolev inequality

DOI10.1214/009117906000000287zbMATH Open1115.60021arXivmath/0511607OpenAlexW2081116272MaRDI QIDQ858978FDOQ858978

Authors: Raphaël Rossignol 

Publication date: 12 January 2007

Published in: The Annals of Probability (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0511607

Recommendations

• Influences of variables and threshold intervals under group symmetries
• On Russo's approximate zero-one law
• scientific article; zbMATH DE number 1302648
• Influence and sharp-threshold theorems for monotonic measures
• Arbitrary Threshold Widths for Monotone, Symmetric Properties

zbMATH Keywords

thresholdinfluencelogarithmic Sobolev inequality

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Measures and integrals in product spaces (28A35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Inequalities in Fourier analysis
• Concentration inequalities using the entropy method
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial methods in density estimation
• On Russo's approximate zero-one law
• Concentration of measure and isoperimetric inequalities in product spaces
• Every monotone graph property has a sharp threshold
• A new look at independence
• Title not available (Why is that?)
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Sharp thresholds of graph properties, and the $k$-sat problem
• The Evolution of Random Graphs
• Influences of variables and threshold intervals under group symmetries
• Title not available (Why is that?)
• First passage percolation has sublinear distance variance.
• Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
• On Talagrand's deviation inequalities for product measures
• An approximate zero-one law
• The scaling window of the 2-SAT transition
• Title not available (Why is that?)
• Satisfiability threshold for random XOR-CNF formulas
• Image denoising by statistical area thresholding

Cited In (15)

• The sharp threshold for percolation on expander graphs
• Approximate zero-one laws and sharpness of the percolation transition in a class of models including two-dimensional Ising percolation
• Submean variance bound for effective resistance of random electric networks
• On Russo's approximate zero-one law
• A stability result for the cube edge isoperimetric inequality
• Exponential concentration for first passage percolation through modified Poincaré inequalities
• A Symmetric Density Property: Monotonicity and the Approximate Symmetric Derivative
• Sublinear variance in first-passage percolation for general distributions
• Reed-Muller Codes
• Arbitrary Threshold Widths for Monotone, Symmetric Properties
• Thresholds and expectation-thresholds of monotone properties with small minterms
• Almost isoperimetric subsets of the discrete cube
• Talagrand's influence inequality revisited
• Edge-Isoperimetric Inequalities and Influences
• Sharp threshold for percolation on expanders

This page was built for publication: Threshold for monotone symmetric properties through a logarithmic Sobolev inequality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q858978)