Every monotone graph property has a sharp threshold

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

Recommendations

scientific article; zbMATH DE number 1984544
Monotone properties of random geometric graphs have sharp thresholds
Every monotone graph property is testable
Every Monotone Graph Property Is Testable
Sharp thresholds for monotone properties in random geometric graphs
A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
On the typical structure of graphs in a monotone property
The property of having a $k$-regular subgraph has a sharp threshold
Monotone Bipartite Graph Properties are Evasive
A lower bound for the complexity of monotone graph properties

Cites work

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 53883 (Why is no real title available?)
scientific article; zbMATH DE number 3503316 (Why is no real title available?)
An approximate zero-one law
Finite Permutation Groups and Finite Simple Groups
Inequalities in Fourier analysis
Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
On the critical percolation probabilities
The influence of variables in product spaces
Threshold functions

Cited in

(only showing first 100 items - show all)

Arbitrary Threshold Widths for Monotone, Symmetric Properties
On the power of choice for Boolean functions
Interview with Gil Kalai
The critical probability for confetti percolation equals 1/2
On symmetric intersecting families of vectors
Bootstrap percolation on the Hamming torus
Phase transition of degeneracy in minor-closed families
Cryptographic Boolean functions with biased inputs
Majority is stablest: discrete and SoS
Improved approximation of linear threshold functions
Not all interventions are equal for the height of the second peak
Threshold for monotone symmetric properties through a logarithmic Sobolev inequality
The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
The fundamental group of random 2-complexes.
Plane and planarity thresholds for random geometric graphs
Sharp thresholds for monotone non-Boolean functions and social choice theory
Decision Trees and Influences of Variables Over Product Probability Spaces
Talagrand's influence inequality revisited
When are sequences of Boolean functions tame?
Sharp threshold for percolation on expanders
Percolation of even sites for enhanced random sequential adsorption
More on the colorful monochromatic connectivity
Edge-Isoperimetric Inequalities and Influences
On a biased edge isoperimetric inequality for the discrete cube
scientific article; zbMATH DE number 6351493 (Why is no real title available?)
Erratum to: percolation on random Johnson-Mehl tessellations and related models
The Fourier entropy-influence conjecture for certain classes of Boolean functions
Smooth Gaussian fields and percolation
Critical point and duality in planar lattice models
Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
Topological properties of random wireless networks
Sharpness versus robustness of the percolation transition in 2D contact processes
Noise sensitivity and Voronoi percolation
A hierarchy of randomness for graphs
Approximate zero-one laws and sharpness of the percolation transition in a class of models including two-dimensional Ising percolation
On connectivity and robustness of random graphs with inhomogeneity
Complexity of quantum circuits via sensitivity, magic, and coherence
scientific article; zbMATH DE number 7561760 (Why is no real title available?)
Linear transformations of monotone functions on the discrete cube
$\mathcal{U}$-bootstrap percolation: critical probability, exponential decay and applications
Combinatorial and computational aspects of graph packing and graph decomposition
Regular intersecting families
The self-dual point of the two-dimensional random-cluster model is critical for q 1
Exponential decay of connection probabilities for subcritical Voronoi percolation in $\mathbb{R}^d$
On the failure of concentration for the _-ball
On symmetric 3-wise intersecting families
A note on the warmth of random graphs with given expected degrees
Sharp thresholds for the random-cluster and Ising models
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
Slow convergence in bootstrap percolation
Geometric influences
On regular 3-wise intersecting families
A structure theorem for Boolean functions with small total influences
Primitive permutation groups satisfying the small orbit property and a problem of Bourgain and Kalai
scientific article; zbMATH DE number 1984544 (Why is no real title available?)
Asymptotic behavior of finite permutation groups acting on subsets.
Thresholds and Expectation Thresholds
Continuous phase transitions on Galton–Watson trees
Boolean functions: influence, threshold and noise
Upper bounds on Fourier entropy
A tutorial survey of topics in wireless networking. II
On symmetric intersecting families
Approximating the influence of monotone Boolean functions in $O(\sqrt{n})$ query complexity
Shadows of ordered graphs
Sharp thresholds of graph properties, and the $k$-sat problem
Sharpness of the percolation transition in the two-dimensional contact process
Hunting for sharp thresholds
Random sum-free subsets of abelian groups
Empty region graphs
Monotone properties of random geometric graphs have sharp thresholds
The Park-Pham theorem with optimal convergence rate
Influence and sharp-threshold theorems for monotonic measures
A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
Further results on the rainbow vertex-disconnection of graphs
Hypercontractivity for global functions and sharp thresholds
Rainbow $k$-connectivity of random bipartite graphs
Noise sensitivity of Boolean functions and applications to percolation
Noise stability of functions with low influences: invariance and optimality
Percolation on finite graphs and isoperimetric inequalities.
A stability result for the cube edge isoperimetric inequality
On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes
A simple reduction from a biased measure on the discrete cube to the uniform measure
Around two theorems and a lemma by Lucio Russo
Percolation on random Johnson-Mehl tessellations and related models
The mathematics and statistics of voting power
A Harris-Kesten theorem for confetti percolation
Moments of graphs in monotone families
A note on the Harris-Kesten theorem
Towards a proof of the Fourier-entropy conjecture?
Generalized nonlinearity of $S$-boxes
A Sharp Threshold for Network Reliability
Properties of atypical graphs from negative complexities
Another look at the phenomenon of phase transition
Rainbow monochromatic $k$-edge-connection colorings of graphs
On the influences of variables on Boolean functions in product spaces
On topological minors in random simplicial complexes
Supercritical percolation on finite transitive graphs I: uniqueness of the giant component
The sharp threshold for bootstrap percolation in all dimensions
Maximal planar subgraphs of fixed girth in random graphs
Complexity-theoretic models of phase transitions in search problems

This page was built for publication: Every monotone graph property has a sharp threshold

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