Sharp thresholds For monotone properties in random geometric graphs

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 d ≥ 2. 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.

REFERENCES

• 1: Martin J. B. Appel and Ralph P. Russo, The connectivity of a graph on uniform points on {0,1}d, Statistics & Probability Letters, 60 (2002), 351--7.
• 2: Lorna Booth, Jehoshua Bruck, Massimo Franceschetti, and Ronald Meester, Covering algorithms, continuum percolation and the geometry of wireless networks, The Annals of Applied Probability, 13 (2003), no. 2, 722--41.
• 3: Jean Bourgain and Gil Kalai, Influences of variables and threshold intervals under group symmetries, Geometric Functional Analysis (1997).
• 4: Béla Bollobás, Random graphs, Cambridge studies in advanced mathematics, vol. 73, Cambridge University Press, New York, 2001.
• 5: Josep Díaz, Mathew D. Penrose, Jordi Petit, and María Sema, Approximating layout problems on geometric random grapphs, Tech. Report TR-417-98, Algorithms and Complexity in Information Technology, 1998.
• 6: Richard Durrett, Probability: Theory and Examples, second ed., Duxbury Press, 1996.
• 7: Pál Erdos and Alfréd Renyi, On random graphs I, Publicationes Mathimaticae Debrecen (1959).
• 8: Pál Erdos and Alfréd Renyi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kut. Int. Kozl., 5 (1960), 17--61.
• 9: Ehud Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proceedings of the American Mathematical Society 124 (1996), 2993--3002.
• 10: Erhard Godehardt , Jerzy Jaworski, On the connectivity of a random interval graph, Random Structures & Algorithms, v.9 n.1-2, p.137-161, Aug./Sept. 1996
• 11: Piyush Gupta and Panganmala R. Kumar, Stochastic analysis, control, optimization and applications: A volume in honor of W.H. Fleming, ch. Critical power for asymptotic connectivity in wireless networks, Birkhaüser, Boston, 1998.
• 12: Piyush Gupta and Panganmala~R. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory IT-46 (2000), no. 2, 388--404.
• 13: Piyush Gupta and Panganmala~R. Kumar, Internets in the sky: The capacity of three dimensional wireless networks, Communications in Information and Systems 1 (2001), no. 1, 33--50.
• 14: Erhard Godehardt, Graphs as structural models: the applications of graphs and multigraphs in cluster analysis, Vieweg, Brunswick, 1990.
• 15: Alexander Holroyd and Yuval Peres, Trees and matchings from point processes, Electronic communications in probability 8 (2003), no. Paper 3, 17--27.
• 16: Jordi Petit i Silvestre, Layout problems, Ph.D. thesis, Universitat Politècnica de Catalunya, Barcelona, 25 May 2001.
• 17: Svante Janson, Tomasz Luczak, and Andrzej Ruciński, Random graphs, Wiley-Interscience series in discrete mathematics and optimization, Wiley-Interscience, New York, 2000.
• 18: Bhaskar Krishnamachari, Stephen Wicker, Ramon Bejar, and Marc Pearlman, Communications, information and network security, ch. Critical Density Thresholds in Distributed Wireless Networks, Kluwer, December 2002.
• 19: Tom Leighton and Peter W. Shor, Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms, Combinatorica 9 (1989), 161--87.
• 20: Gregory McColm, Threshold functions for random graphs on a line segment, Submitted for publication.
• 21: S. Muthukrishnan and Gopal Pandurangan, The bin-covering technique for thresholding random geometric graph properties, Tech. Report 2003-39, DIMACS, November 2003.
• 22: Valery B. Nevzorov, Records: A mathematical theory, Translations of Mathematical Monographs, vol. 194, American Mathematical Society, Providence, Rhode Island, 2001.
• 23: Mathew D. Penrose, The longest edge of the random minimal spanning tree, The Annals of Applied Probability 7 (1997), no. 2, 340--61.
• 24: Mathew D. Penrose, Random geometric graphs, Oxford Studies in Probability, vol. 5, Oxford University Press, May 2003.
• 25: S. Shakkottai, R. Srikant, and N. B. Shroff, Unreliable sensor grids: coverage, connectivity and diameter, Proc. Infocom 2003.
• 26: Peter W. Shor and Joseph E. Yukich, Minmax grid matching and empirical measures, The Annals of Probability 19 (1991), no. 3, 1338--48.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Design, Theory

Keywords:
geometric random graphs, sharp thresholds, wireless networks