<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Infinite Random Geometric Graphs
Anthony Bonato1 and Jeannette Janssen2
1Department of Mathematics, Ryerson University, Toronto, ON M5B 2K3, Canada
abonato@ryerson.ca
2Department of Mathematics and Statistics, Dalhousie University, Halifax, NS B3H 3J5,
Canada
janssen@mathstat.dal.ca
Annals of Combinatorics 15 (4) pp.549-563 December, 2011
AMS Subject Classification: 05C75, 05C80, 46B04, 54E35
Abstract:
We introduce a new class of countably infinite random geometric graphs, whose
vertices V are points in a metric space, and vertices are adjacent independently with probability
p ∈ (0, 1) if the metric distance between the vertices is below a given threshold. For
certain choices of V as a countable dense set in Rn equipped with the metric derived from
the L∞-norm, it is shown that with probability 1 such infinite random geometric graphs have
a unique isomorphism type. The isomorphism type, which we call GRn, is characterized by a
geometric analogue of the existentially closed adjacency property, and we give a deterministic
construction of GRn. In contrast, we show that infinite random geometric graphs in R2 with
the Euclidean metric are not necessarily isomorphic.
Keywords: graphs, geometric graphs, adjacency property, random graphs, metric spaces, isometry

References:

1. Aiello,W., Bonato, A., Cooper, C., Janssen, J., Prałat, P.: A spatial web graph model with
local influence regions. Internet Math. 5(1-2), 175–196 (2009)
2. Balister, P., Bollob´as, B., Sarkar, A., Walters, M.: Highly connected random geometric
graphs. Discrete Appl. Math. 157(2), 309–320 (2009)
3. Bonato, A.: A Course on the Web Graph. AMS, Providence, Rhode Island (2008)
4. Bonato, A., Janssen, J.: Infinite limits and adjacency properties of a generalized copying
model. Internet Math. 4(2-3), 199–223 (2009)
5. Bonato, A., Janssen, J., Prałat, P.: The geometric protean model for on-line social networks.
Lecture Notes in Comput. Sci. 6516, 110–121 (2010)
6. Bryant, V.: Metric Spaces: Iteration and Application. Cambridge University Press, Cambridge
(1985)
7. Cameron, P.J.: The random graph. In: Graham, R.L., Neˇsetˇril, J. (eds.) Algorithms and
Combinatorics, 14, pp. 333–351. Springer Verlag, Berlin (1997)
8. Cameron, P.J.: The random graph revisited. In: Casacuberta, C., Mir´o-Roig, R.M.,
Verdera, J., Xamb´o-Descamps, S. (eds.) European Congress of Mathematics, Vol. I, pp.
267–274. Birkhauser, Basel (2001)
9. Chung, F., Lu, L.: Complex Graphs and Networks. AMS, Providence, Rhode Island
(2006)
10. Ellis, R., Jia, X., Yan, C.H.: On random points in the unit disk. Random Algorithm and
Structures 29(1), 14–25 (2006)
11. Erd˝os, P., R´enyi, A.: Asymmetric graphs. Acta Math. Acad. Sci. Hungar 14, 295–315
(1963)
12. Flaxman, A., Frieze, A.M., Vera, J.: A geometric preferential attachment model of networks.
Internet Math. 3(2), 187–205 (2006)
13. Frieze, A.M., Kleinberg, J., Ravi, R., Debany, W.: Line of sight networks. Combin.
Probab. Comput. 18(1-2), 145–163 (2009)
14. Goel, A., Rai, S., Krishnamachari, B.: Monotone properties of random geometric graphs
have sharp thresholds. Ann. Appl. Probab. 15(4), 2535–2552 (2005)
15. Kleinberg, R.D., Kleinberg, J.M.: Isomorphism and embedding problems for infinite limits
of scale-free graphs. In: Proceedings of the sixteenth annual ACM-SIAM symposium
on Discrete algorithms, pp. 277–286 (electronic). ACM, New York (2005)

Penrose, M.: Random Geometric Graphs. Oxford University Press, Oxford (2003)
17. West, D.B.: Introduction to Graph Theory, 2nd Edition. Prentice Hall, New Jersey (2001)