On Sharp Thresholds in Random Geometric Graphs

Autor:	Bradonjić, Milan, Perkins, Will
Rok vydání:	2013
Předmět:	Mathematics - Probability Computer Science - Computational Complexity Computer Science - Discrete Mathematics Mathematics - Combinatorics
Druh dokumentu:	Working Paper
DOI:	10.4230/LIPIcs.APPROX-RANDOM.2014.500
Popis:	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. Comment: Replaces an earlier version with the title "Thresholds for Random Geometric k-SAT"
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1308.1084 Zobrazit plný text záznamu View this record from Arxiv