Every monotone graph property has a sharp threshold

DOI10.1090/S0002-9939-96-03732-XzbMath0864.05078OpenAlexW1529556207WikidataQ62111471 ScholiaQ62111471MaRDI QIDQ4717065

Publication date: 22 June 1997

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0002-9939-96-03732-x

zbMATH Keywords

random graphs isoperimetric inequalities threshold monotone graph property conjecture of Linial

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Measures and integrals in product spaces (28A35)

Related Items

On connectivity and robustness of random graphs with inhomogeneity, On symmetric intersecting families of vectors, Continuous phase transitions on Galton–Watson trees, Hypercontractivity for global functions and sharp thresholds, Influence of a Set of Variables on a Boolean Function, Rainbow connectivity and rainbow index of inhomogeneous random graphs, Interview with Gil Kalai, Transitive closure in a polluted environment, Talagrand's influence inequality revisited, Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions, Smooth Gaussian fields and percolation, KKL's influence on me, A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses, Noise sensitivity of Boolean functions and applications to percolation, On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes, Unnamed Item, Reed-Muller Codes, Bootstrap percolation on the hypercube, Not all interventions are equal for the height of the second peak, On the failure of concentration for the $\ell_\infty$-ball, Percolation on finite graphs and isoperimetric inequalities., Boolean functions: influence, threshold and noise, Sharp thresholds of graph properties, and the $k$-sat problem, Topological properties of random wireless networks, A note on the Harris-Kesten theorem, Bootstrap percolation in three dimensions, On regular 3-wise intersecting families, Erratum to: percolation on random Johnson-Mehl tessellations and related models, Maximal planar subgraphs of fixed girth in random graphs, Properties of atypical graphs from negative complexities, Around two theorems and a lemma by Lucio Russo, Sharp Thresholds for Monotone Non-Boolean Functions and Social Choice Theory, Threshold for monotone symmetric properties through a logarithmic Sobolev inequality, Influence and sharp-threshold theorems for monotonic measures, A Harris-Kesten theorem for confetti percolation, Upper bounds on Fourier entropy, Upper Bounds on Fourier Entropy, Improved approximation of linear threshold functions, On boundaries and influences, Spectral and structural properties of random interdependent networks, Talagrand inequality at second order and application to Boolean analysis, On the Power of Choice for Boolean Functions, More on the colorful monochromatic connectivity, The Fourier spectrum of critical percolation, A stability result for the cube edge isoperimetric inequality, Sharp thresholds in bootstrap percolation, Rainbow connections of graphs: a survey, Sharp thresholds for the random-cluster and Ising models, Sharpness of the percolation transition in the two-dimensional contact process, Phase transition of degeneracy in minor-closed families, Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome?, Geometric influences, Shadows of ordered graphs, Ultrasensitivity and sharp threshold theorems for multisite systems, On rainbow-$k$-connectivity of random graphs, A structure theorem for Boolean functions with small total influences, A simple reduction from a biased measure on the discrete cube to the uniform measure, On a biased edge isoperimetric inequality for the discrete cube, On symmetric 3-wise intersecting families, Combinatorial and computational aspects of graph packing and graph decomposition, Towards a proof of the Fourier-entropy conjecture?, Oded Schramm's contributions to noise sensitivity, The mathematics and statistics of voting power, Slow convergence in bootstrap percolation, Exponential decay of connection probabilities for subcritical Voronoi percolation in $\mathbb{R}^d$, The sharp threshold for bootstrap percolation in all dimensions, Sharp threshold for percolation on expanders, Another look at the phenomenon of phase transition, Thresholds and expectation-thresholds of monotone properties with small minterms, The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture, Decision Trees and Influences of Variables Over Product Probability Spaces, The phase transition for dyadic tilings, Cryptographic Boolean functions with biased inputs, Approximate zero-one laws and sharpness of the percolation transition in a class of models including two-dimensional Ising percolation, On symmetric intersecting families, The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions, Percolation of even sites for enhanced random sequential adsorption, Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality, Noise sensitivity and Voronoi percolation, Percolation on random Johnson-Mehl tessellations and related models, Bootstrap percolation on the Hamming torus, Noise stability of functions with low influences: invariance and optimality, Asymptotic behavior of finite permutation groups acting on subsets., Random sum-free subsets of abelian groups, Monotone properties of random geometric graphs have sharp thresholds, A note on the entropy/influence conjecture, The self-dual point of the two-dimensional random-cluster model is critical for $q \geqslant 1$, Rainbow $k$-connectivity of random bipartite graphs, Generalized nonlinearity of $S$-boxes, Unnamed Item, On topological minors in random simplicial complexes, Arbitrary Threshold Widths for Monotone, Symmetric Properties, Edge-Isoperimetric Inequalities and Influences, The critical probability for random Voronoi percolation in the plane is 1/2, Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems, Sharpness versus robustness of the percolation transition in 2D contact processes, On the Influences of Variables on Boolean Functions in Product Spaces, Empty region graphs, The fundamental group of random 2-complexes, Rainbow monochromatic $k$-edge-connection colorings of graphs, Further results on the rainbow vertex-disconnection of graphs, Plane and planarity thresholds for random geometric graphs, Mixed connectivity properties of random graphs and some special graphs, Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity, Unnamed Item, The critical probability for confetti percolation equals 1/2, $\mathcal{U}$-bootstrap percolation: critical probability, exponential decay and applications, When are sequences of Boolean functions tame?, Linear transformations of monotone functions on the discrete cube, A tutorial survey of topics in wireless networking. II, Noise sensitivity of the top eigenvector of a Wigner matrix, A note on the warmth of random graphs with given expected degrees, Complexity-theoretic models of phase transitions in search problems, Regular intersecting families, Primitive permutation groups satisfying the small orbit property and a problem of Bourgain and Kalai, A hierarchy of randomness for graphs, Unnamed Item

Cites Work