On sharp thresholds in random geometric graphs

DOI10.4230/LIPICS.APPROX-RANDOM.2014.500zbMATH Open1359.05109arXiv1308.1084MaRDI QIDQ2969641FDOQ2969641

Will Perkins, Milan Bradonjić

Publication date: 22 March 2017

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.

Full work available at URL: https://arxiv.org/abs/1308.1084

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

zbMATH Keywords

random geometric graphssharp thresholds\(k\)-SAT

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25)

Cited In (9)

• 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
• Monotone properties of random geometric graphs have sharp thresholds
• The bin-covering technique for thresholding random geometric graph properties
• Sharp thresholds for certain Ramsey properties of random graphs
• Title not available (Why is that?)
• Plane and planarity thresholds for random geometric graphs
• Title not available (Why is that?)

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)