Monotone properties of random geometric graphs have sharp thresholds

DOI10.1214/105051605000000575MaRDI QIDQ2496499zbMATH OpenOpenAlexFDO

Authors Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari

Publication date 10 July 2006

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

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

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)

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.

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

Cites work

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

Cited in

(17)

• Every monotone graph property has a sharp threshold
• Localization in random geometric graphs with too many edges
• The peculiar phase structure of random graph bisection
• 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)