On Sharp Thresholds in Random Geometric Graphs
Preprint
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.Keywords
All Related Versions
- Version 1, 2013-08-05, ArXiv
- Version 2, 2014-04-22, ArXiv
- Published version: .
This publication has 7 references indexed in Scilit:
- A simple one dimensional glassy Kac modelJournal of Statistical Mechanics: Theory and Experiment, 2007
- Percolation of unsatisfiability in finite dimensionsPhysical Review E, 2004
- The scaling window of the 2‐SAT transitionRandom Structures & Algorithms, 2001
- Sharp thresholds of graph properties, and the $k$-sat problemJournal of the American Mathematical Society, 1999
- Influences of Variables and Threshold Intervals under Group SymmetriesGeometric and Functional Analysis, 1997
- Every monotone graph property has a sharp thresholdProceedings of the American Mathematical Society, 1996
- Effect of the Interface on the Properties of Composite MediaPhysical Review Letters, 1995