Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-02-06T20:49:06.130Z Has data issue: false hasContentIssue false
  • English
  • Français

The Random Connection Model on the Torus

Published online by Cambridge University Press:  09 July 2014

LUC DEVROYE  and
NICOLAS FRAIMAN
LUC DEVROYE
Affiliation:
School of Computer Science, McGill University, Montreal, CanadaH3A 2K6 (e-mail: luc@cs.mcgill.ca)
NICOLAS FRAIMAN
Affiliation:
Department of Mathematics and Statistics, McGill University, Montreal, CanadaH3A 2K6 (e-mail: fraiman@math.mcgill.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We study the diameter of a family of random graphs on the torus that can be used to model wireless networks. In the random connection model two points x and y are connected with probability g(y−x), where g is a given function. We prove that the diameter of the graph is bounded by a constant, which depends only on ‖g‖1, with high probability as the number of vertices in the graph tends to infinity.

Keywords

Primary 60C05Secondary 05C80
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 5: Honouring the Memory of Philippe Flajolet - Part 1 , September 2014 , pp. 796 - 804
Copyright
Copyright © Cambridge University Press 2014 

References

[1]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
[2]Flajolet, P., Hatzis, K. P., Nikoletseas, S. E. and Spirakis, P. G. (2002) On the robustness of interconnections in random graphs: A symbolic approach. Theoret. Comput. Sci. 287 515–534.CrossRefGoogle Scholar
[3]Flajolet, P., Salvy, B. and Schaffer, G. (2004) Airy phenomena and analytic combinatorics of connected graphs. Electron. J. Combin. 11 R34.Google Scholar
[4]Franceschetti, M. and Meester, R. (2008) Random Networks for Communication: From Statistical Physics to Information Systems, Vol. 24 of Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press.Google Scholar
[5]Gilbert, E. (1961) Random plane networks. J. Soc. Ind. Appl. Math. 9 533–543.Google Scholar
[6]Grafakos, L. (2008) Classical Fourier Analysis, Graduate Texts in Mathematics, Springer.Google Scholar
[7]Lagarias, J. C., Odlyzko, A. M. and Zagier, D. B. (1985) On the capacity of disjointly shared networks. Computer Networks and ISDN Systems 10 275–285.Google Scholar
[8]Louchard, G. (1987) Random walks, Gaussian processes and list structures. Theoret. Comput. Sci. 53 99–124.CrossRefGoogle Scholar
[9]Meester, R. and Roy, R. (1996) Continuum Percolation, Vol. 119 of Cambridge Tracts in Mathematics, Cambridge University Press.Google Scholar
[10]Penrose, M. (1991) On a continuum percolation model. Adv. Appl. Probab. 23 536–556.Google Scholar