Threshold for monotone symmetric properties through a logarithmic Sobolev inequality
From MaRDI portal
(Redirected from Publication:858978)
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 . This new bound is shown to be asymptotically optimal.
Recommendations
Cites work
- scientific article; zbMATH DE number 446476 (Why is no real title available?)
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 3904630 (Why is no real title available?)
- scientific article; zbMATH DE number 3503316 (Why is no real title available?)
- scientific article; zbMATH DE number 3504209 (Why is no real title available?)
- scientific article; zbMATH DE number 522891 (Why is no real title available?)
- scientific article; zbMATH DE number 1069282 (Why is no real title available?)
- scientific article; zbMATH DE number 195103 (Why is no real title available?)
- scientific article; zbMATH DE number 3349081 (Why is no real title available?)
- A new look at independence
- An approximate zero-one law
- Combinatorial methods in density estimation
- Concentration inequalities using the entropy method
- Concentration of measure and isoperimetric inequalities in product spaces
- Every monotone graph property has a sharp threshold
- First passage percolation has sublinear distance variance.
- Image denoising by statistical area thresholding
- Inequalities in Fourier analysis
- Influences of variables and threshold intervals under group symmetries
- Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
- On Russo's approximate zero-one law
- On Talagrand's deviation inequalities for product measures
- Satisfiability threshold for random XOR-CNF formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- The Evolution of Random Graphs
- The scaling window of the 2-SAT transition
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
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
- Thresholds and expectation-thresholds of monotone properties with small minterms
- Arbitrary Threshold Widths for Monotone, Symmetric Properties
- Almost isoperimetric subsets of the discrete cube
- Talagrand's influence inequality revisited
- Sharp threshold for percolation on expanders
- Edge-Isoperimetric Inequalities and Influences
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)
