Every monotone graph property has a sharp threshold
From MaRDI portal
Publication:4717065
DOI10.1090/S0002-9939-96-03732-XzbMATH Open0864.05078OpenAlexW1529556207WikidataQ62111471 ScholiaQ62111471MaRDI QIDQ4717065FDOQ4717065
Authors: Ehud Friedgut, Gil Kalai 
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
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
Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Measures and integrals in product spaces (28A35)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Inequalities in Fourier analysis
- Title not available (Why is that?)
- The influence of variables in product spaces
- Finite Permutation Groups and Finite Simple Groups
- On the critical percolation probabilities
- Threshold functions
- Title not available (Why is that?)
- Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
- An approximate zero-one law
Cited In (only showing first 100 items - show all)
- Sharpness versus robustness of the percolation transition in 2D contact processes
- Approximate zero-one laws and sharpness of the percolation transition in a class of models including two-dimensional Ising percolation
- Linear transformations of monotone functions on the discrete cube
- On symmetric 3-wise intersecting families
- Exponential decay of connection probabilities for subcritical Voronoi percolation in \(\mathbb{R}^d\)
- Combinatorial and computational aspects of graph packing and graph decomposition
- The self-dual point of the two-dimensional random-cluster model is critical for \(q \geqslant 1\)
- On the failure of concentration for the \(\ell_\infty\)-ball
- Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
- Sharp thresholds for the random-cluster and Ising models
- On regular 3-wise intersecting families
- Slow convergence in bootstrap percolation
- Geometric influences
- A structure theorem for Boolean functions with small total influences
- Thresholds and Expectation Thresholds
- Asymptotic behavior of finite permutation groups acting on subsets.
- Sharp thresholds of graph properties, and the $k$-sat problem
- A tutorial survey of topics in wireless networking. II
- Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
- On symmetric intersecting families
- Hunting for sharp thresholds
- Sharpness of the percolation transition in the two-dimensional contact process
- Monotone properties of random geometric graphs have sharp thresholds
- Empty region graphs
- Noise sensitivity of Boolean functions and applications to percolation
- Influence and sharp-threshold theorems for monotonic measures
- Further results on the rainbow vertex-disconnection of graphs
- Percolation on finite graphs and isoperimetric inequalities.
- Noise stability of functions with low influences: invariance and optimality
- On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes
- A stability result for the cube edge isoperimetric inequality
- A simple reduction from a biased measure on the discrete cube to the uniform measure
- 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
- On the influences of variables on Boolean functions in product spaces
- Properties of atypical graphs from negative complexities
- The sharp threshold for bootstrap percolation in all dimensions
- On topological minors in random simplicial complexes
- Complexity-theoretic models of phase transitions in search problems
- The critical probability for random Voronoi percolation in the plane is 1/2
- Oded Schramm's contributions to noise sensitivity
- A note on the entropy/influence conjecture
- On boundaries and influences
- Bootstrap percolation on the hypercube
- Bootstrap percolation in three dimensions
- Upper bounds on Fourier entropy
- On rainbow-\(k\)-connectivity of random graphs
- The Fourier spectrum of critical percolation
- Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome?
- Arbitrary Threshold Widths for Monotone, Symmetric Properties
- On the power of choice for Boolean functions
- Sharp thresholds in bootstrap percolation
- Thresholds and expectation-thresholds of monotone properties with small minterms
- The critical probability for confetti percolation equals 1/2
- Noise sensitivity of the top eigenvector of a Wigner matrix
- Majority is stablest: discrete and SoS
- Cryptographic Boolean functions with biased inputs
- The fundamental group of random 2-complexes.
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Improved approximation of linear threshold functions
- Threshold for monotone symmetric properties through a logarithmic Sobolev inequality
- Decision Trees and Influences of Variables Over Product Probability Spaces
- Edge-Isoperimetric Inequalities and Influences
- Sharp threshold for percolation on expanders
- Percolation of even sites for enhanced random sequential adsorption
- More on the colorful monochromatic connectivity
- Title not available (Why is that?)
- Erratum to: percolation on random Johnson-Mehl tessellations and related models
- The Fourier entropy-influence conjecture for certain classes of Boolean functions
- Topological properties of random wireless networks
- On connectivity and robustness of random graphs with inhomogeneity
- Complexity of quantum circuits via sensitivity, magic, and coherence
- A hierarchy of randomness for graphs
- Noise sensitivity and Voronoi percolation
- Title not available (Why is that?)
- \(\mathcal{U}\)-bootstrap percolation: critical probability, exponential decay and applications
- Regular intersecting families
- A note on the warmth of random graphs with given expected degrees
- Title not available (Why is that?)
- Continuous phase transitions on Galton–Watson trees
- Primitive permutation groups satisfying the small orbit property and a problem of Bourgain and Kalai
- Upper bounds on Fourier entropy
- Boolean functions: influence, threshold and noise
- Shadows of ordered graphs
- Random sum-free subsets of abelian groups
- The Park-Pham theorem with optimal convergence rate
- A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
- Hypercontractivity for global functions and sharp thresholds
- Rainbow \(k\)-connectivity of random bipartite graphs
- Around two theorems and a lemma by Lucio Russo
- A note on the Harris-Kesten theorem
- Another look at the phenomenon of phase transition
- A Sharp Threshold for Network Reliability
- Towards a proof of the Fourier-entropy conjecture?
- Generalized nonlinearity of \(S\)-boxes
- Supercritical percolation on finite transitive graphs I: uniqueness of the giant component
- Rainbow monochromatic \(k\)-edge-connection colorings of graphs
- Maximal planar subgraphs of fixed girth in random graphs
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)
