Every monotone graph property has a sharp threshold
From MaRDI portal
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
- An approximate zero-one law
- Finite Permutation Groups and Finite Simple Groups
- 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?)
- 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)- Empty region graphs
- Linear transformations of monotone functions on the discrete cube
- A tutorial survey of topics in wireless networking. II
- On boundaries and influences
- Sharp thresholds in bootstrap percolation
- The mathematics and statistics of voting power
- Complexity-theoretic models of phase transitions in search problems
- Boolean functions: influence, threshold and noise
- Maximal planar subgraphs of fixed girth in random graphs
- Around two theorems and a lemma by Lucio Russo
- Spectral and structural properties of random interdependent networks
- More on the colorful monochromatic connectivity
- A stability result for the cube edge isoperimetric inequality
- Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome?
- On a biased edge isoperimetric inequality for the discrete cube
- Exponential decay of connection probabilities for subcritical Voronoi percolation in \(\mathbb{R}^d\)
- Generalized nonlinearity of S-boxes
- Percolation on finite graphs and isoperimetric inequalities.
- On symmetric intersecting families
- Noise sensitivity and Voronoi percolation
- Random sum-free subsets of abelian groups
- Rainbow \(k\)-connectivity of random bipartite graphs
- Rainbow monochromatic \(k\)-edge-connection colorings of graphs
- Further results on the rainbow vertex-disconnection of graphs
- Mixed connectivity properties of random graphs and some special graphs
- \(\mathcal{U}\)-bootstrap percolation: critical probability, exponential decay and applications
- When are sequences of Boolean functions tame?
- Not all interventions are equal for the height of the second peak
- Talagrand inequality at second order and application to Boolean analysis
- Towards a proof of the Fourier-entropy conjecture?
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Bootstrap percolation on the Hamming torus
- A note on the warmth of random graphs with given expected degrees
- Regular intersecting families
- Primitive permutation groups satisfying the small orbit property and a problem of Bourgain and Kalai
- Topological properties of random wireless networks
- A note on the Harris-Kesten theorem
- Shadows of ordered graphs
- Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
- Percolation on random Johnson-Mehl tessellations and related models
- Monotone properties of random geometric graphs have sharp thresholds
- The critical probability for random Voronoi percolation in the plane is 1/2
- Sharpness versus robustness of the percolation transition in 2D contact processes
- A hierarchy of randomness for graphs
- Phase transition of degeneracy in minor-closed families
- On the failure of concentration for the _-ball
- On topological minors in random simplicial complexes
- Ultrasensitivity and sharp threshold theorems for multisite systems
- On symmetric 3-wise intersecting families
- The Fourier entropy-influence conjecture for certain classes of Boolean functions
- On the influences of variables on Boolean functions in product spaces
- The fundamental group of random 2-complexes.
- Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
- On regular 3-wise intersecting families
- scientific article; zbMATH DE number 6351493 (Why is no real title available?)
- A Harris-Kesten theorem for confetti percolation
- Upper bounds on Fourier entropy
- Moments of graphs in monotone families
- Thresholds and Expectation Thresholds
- Upper bounds on Fourier entropy
- Sharp thresholds for monotone non-Boolean functions and social choice theory
- Decision Trees and Influences of Variables Over Product Probability Spaces
- Improved approximation of linear threshold functions
- Sharp thresholds of graph properties, and the k-sat problem
- Geometric influences
- On rainbow-k-connectivity of random graphs
- scientific article; zbMATH DE number 1984544 (Why is no real title available?)
- 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
- Combinatorial and computational aspects of graph packing and graph decomposition
- Critical point and duality in planar lattice models
- Hunting for sharp thresholds
- A Sharp Threshold for Network Reliability
- Thresholds and expectation-thresholds of monotone properties with small minterms
- The critical probability for confetti percolation equals 1/2
- Cryptographic Boolean functions with biased inputs
- scientific article; zbMATH DE number 7561760 (Why is no real title available?)
- On the power of choice for Boolean functions
- Percolation of even sites for enhanced random sequential adsorption
- Hypergraph removal lemmas via robust sharp threshold theorems
- Plane and planarity thresholds for random geometric graphs
- The sharp threshold for bootstrap percolation in all dimensions
- The phase transition for dyadic tilings
- Arbitrary Threshold Widths for Monotone, Symmetric Properties
- Edge-Isoperimetric Inequalities and Influences
- Asymptotic behavior of finite permutation groups acting on subsets.
- Another look at the phenomenon of phase transition
- Majority is stablest: discrete and SoS
- Reed-Muller Codes
- On connectivity and robustness of random graphs with inhomogeneity
- On symmetric intersecting families of vectors
- Continuous phase transitions on Galton–Watson trees
- 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
- 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
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)
