Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-14T17:22:53.233Z 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: [email protected])
NICOLAS FRAIMAN
Affiliation:
Department of Mathematics and Statistics, McGill University, Montreal, CanadaH3A 2K6 (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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