Monotone properties of random geometric graphs have sharp thresholds

DOI10.1214/105051605000000575zbMATH Open1098.60011arXivmath/0310232OpenAlexW2037549896MaRDI QIDQ2496499FDOQ2496499

Authors: Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari 

Publication date: 10 July 2006

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: Random geometric graphs result from taking $n$ uniformly distributed points in the unit cube, $[0,1{]}^d$, and connecting two points if their Euclidean distance is at most $r$, for some prescribed $r$. We show that monotone properties for this class of graphs have sharp thresholds by reducing the problem to bounding the bottleneck matching on two sets of $n$ points distributed uniformly in $[0,1{]}^d$. We present upper bounds on the threshold width, and show that our bound is sharp for $d=1$ and at most a sublogarithmic factor away for $dge2$. Interestingly, the threshold width is much sharper for random geometric graphs than for Bernoulli random graphs. Further, a random geometric graph is shown to be a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for Bernoulli random graphs.

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

Recommendations

• Sharp thresholds for monotone properties in random geometric graphs
• On sharp thresholds in random geometric graphs
• Plane and planarity thresholds for random geometric graphs
• Random Geometric Graphs
• Sharp thresholds of graph properties, and the $k$-sat problem

zbMATH Keywords

wireless networksgeometric random graphssharp thresholds

Mathematics Subject Classification ID

Group preferences (91B10) Geometric probability and stochastic geometry (60D05) Applications of global differential geometry to the sciences (53C80)

Cites Work

• Random Geometric Graphs
• Title not available (Why is that?)
• Probability. Theory and examples.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Random graphs.
• Title not available (Why is that?)
• Minimax grid matching and empirical measures
• Records. Mathematical theory.
• Every monotone graph property has a sharp threshold
• The capacity of wireless networks
• The longest edge of the random minimal spanning tree
• On the connectivity of a random interval graph
• Influences of variables and threshold intervals under group symmetries
• The connectivity of a graph on uniform points on [0,\,1]\(^{d}\).
• The bin-covering technique for thresholding random geometric graph properties
• Threshold Functions for Random Graphs on a Line Segment
• Trees and matchings from point processes
• Covering algorithms, continuum percolation and the geometry of wireless networks
• Title not available (Why is that?)
• Internets in the sky: The capacity of three dimensional wireless networks

Cited In (17)

• Every monotone graph property has a sharp threshold
• The peculiar phase structure of random graph bisection
• Localization in random geometric graphs with too many edges
• On sharp thresholds in random geometric graphs
• Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
• Random geometric graph: some recent developments and perspectives
• Frugal Routing on Wireless Ad-Hoc Networks
• Sharp threshold for embedding balanced spanning trees in random geometric graphs
• Sharp thresholds for monotone properties in random geometric graphs
• On the equivalence between random graph models
• Burning graphs: a probabilistic perspective
• On the treewidth of random geometric graphs and percolated grids
• Searching for (sharp) thresholds in random structures: where are we now?
• Plane and planarity thresholds for random geometric graphs
• Infinite random geometric graphs
• Clique colourings of geometric graphs
• Geometric random graphs and Rado sets in sequence spaces

This page was built for publication: Monotone properties of random geometric graphs have sharp thresholds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2496499)