On sharp thresholds in random geometric graphs
From MaRDI portal
(Redirected from Publication:2969641)
Abstract: We give a characterization of vertex-monotone properties with sharp thresholds in a Poisson random geometric graph or hypergraph. As an application we show that a geometric model of random k-SAT exhibits a sharp threshold for satisfiability.
Recommendations
- Sharp thresholds for monotone properties in random geometric graphs
- Monotone properties of random geometric graphs have sharp thresholds
- Sharp thresholds of graph properties, and the k-sat problem
- Sharpness of the satisfiability threshold for non-uniform random \(k\)-SAT
- Sharp thresholds for constraint satisfaction problems and homomorphisms
Cited in
(11)- Bounds on the satisfiability threshold for power law distributed random SAT
- Solving non-uniform planted and filtered random SAT formulas greedily
- On smoothed analysis in dense graphs and formulas
- Sharp threshold for embedding balanced spanning trees in random geometric graphs (extended abstract)
- Monotone properties of random geometric graphs have sharp thresholds
- Sharp threshold for embedding balanced spanning trees in random geometric graphs
- Sharp thresholds for monotone properties in random geometric graphs
- The bin-covering technique for thresholding random geometric graph properties
- Sharp thresholds for certain Ramsey properties of random graphs
- Plane and planarity thresholds for random geometric graphs
- scientific article; zbMATH DE number 7561554 (Why is no real title available?)
This page was built for publication: On sharp thresholds in random geometric graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969641)
