<%@ 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
2Department of Mathematics and Statistics, Dalhousie University, Halifax, NS B3H 3J5,
Annals of Combinatorics 15 (4) pp.549-563 December, 2011
AMS Subject Classification: 05C75, 05C80, 46B04, 54E35
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


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
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
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
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)