On Sharp Thresholds in Random Geometric Graphs

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.

Replaces an earlier version with the title "Thresholds for Random Geometric k-SAT"

References in corpus (1)

• A simple one dimensional glassy Kac model

Cited by in corpus (1)

• Directed Random Geometric Graphs