Every monotone graph property has a sharp threshold
From MaRDI portal
Publication:4717065
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
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 (only showing first 100 items - show all)
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Threshold functions
- Inequalities in Fourier analysis
- Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
- The influence of variables in product spaces
- On the critical percolation probabilities
- Finite Permutation Groups and Finite Simple Groups
- An approximate zero-one law
This page was built for publication: Every monotone graph property has a sharp threshold
