Strong noise sensitivity and random graphs

DOI10.1214/14-AOP959zbMath1339.82005arXiv1306.6373OpenAlexW2161066177MaRDI QIDQ5962538

Eyal Lubetzky, Jeffrey E. Steif

Publication date: 12 February 2016

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

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

zbMATH Keywords

random graphsnoise sensitivity of Boolean functions

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Percolation (82B43) Time-dependent percolation in statistical mechanics (82C43)

Related Items

Exceptional times of the critical dynamical Erdős-Rényi graph ⋮ Volatility of Boolean functions ⋮ Hypercontractivity for global functions and sharp thresholds ⋮ Noise sensitivity of percolation via differential inequalities ⋮ Noise sensitivity of critical random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On family trees and subtrees of simple branching processes
• Quantitative noise sensitivity and exceptional times for percolation
• Two moments suffice for Poisson approximations: The Chen-Stein method
• Quantitative relation between noise sensitivity and influences
• Probability on Trees and Networks
• Sharp thresholds of graph properties, and the $k$-sat problem
• The Diameter of Sparse Random Graphs
• The isoperimetric constant of the random graph process
• Lectures on noise sensitivity and percolation
• Noise sensitivity of Boolean functions and applications to percolation