Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-24T14:05:01.172Z Has data issue: false hasContentIssue false
  • English
  • Français

Generating Infinite Random Graphs

Part of: Graph theory Combinatorial probability

Published online by Cambridge University Press:  22 May 2018

Csaba Biró  and
Udayan B. Darji
Csaba Biró
Affiliation:
Department of Mathematics, University of Louisville, Louisville, KY 40292, USA ([email protected]; [email protected])
Udayan B. Darji*
Affiliation:
Department of Mathematics, University of Louisville, Louisville, KY 40292, USA ([email protected]; [email protected])
*
*Corresponding author.
Get access Rights & Permissions [Opens in a new window]

Abstract

We define a growing model of random graphs. Given a sequence of non-negative integers {dn}n=0∞ with the property that di≤i, we construct a random graph on countably infinitely many vertices v0, v1… by the following process: vertex vi is connected to a subset of {v0, …, vi−1} of cardinality di chosen uniformly at random. We study the resulting probability space. In particular, we give a new characterization of random graphs, and we also give probabilistic methods for constructing infinite random trees.

Keywords

Erdős–Rényi graphrandom graphinfinite graphtreeshomogeneous structure

MSC classification

Primary: 05C63: Infinite graphs 05C80: Random graphs
Secondary: 05C05: Trees 60C99: None of the above, but in this section
Type
Research Article
Information
Proceedings of the Edinburgh Mathematical Society , Volume 61 , Issue 3 , August 2018 , pp. 847 - 868
Copyright
Copyright © Edinburgh Mathematical Society 2018 

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.Barabási, A.-L. and Albert, R., Emergence of scaling in random networks, Science 286(5439) (1999), 509–512.Google Scholar
2.Bollobás, B. and Riordan, O. M., The diameter of a scale-free random graph, Combinatorica 24(1) (2004), 5–34.CrossRefGoogle Scholar
3.Bonato, A., The search for n-e.c. graphs, Contrib. Discrete Math. 4(1) (2009), 40–53.Google Scholar
4.Bonato, A. and Janssen, J. C. M., Infinite limits and adjacency properties of a generalized copying model, Internet Math. 4(2–3) (2007), 199–223.CrossRefGoogle Scholar
5.Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T. and Vesztergombi, K. L., Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math. 219(6) (2008), 1801–1851.Google Scholar
6.Brusss, F. T., A counterpart of the Borel-Cantelli lemma, J. Appl. Probab. 17(4) (1980), 1094–1101.CrossRefGoogle Scholar
7.Cameron, P. J., The random graph revisited, European congress of mathematics, volume I (Barcelona, 2000), Progress in Mathematics, Volume 201, pp. 267–274 (Birkhäuser, Basel, 2001).Google Scholar
8.Darji, U. B. and Mitchell, J. D., Approximation of automorphisms of the rationals and the random graph, J. Group Theory 14(3) (2011), 361–388.Google Scholar
9.Diestel, R., Graph theory, 4th edition, Graduate Texts in Mathematics, Volume 173 (Springer, 2010).Google Scholar
10.Erdős, P. and Rényi, A., Asymmetric graphs, Acta Math. Acad. Sci. Hung. 14 (1963), 295–315.Google Scholar
11.Janson, S. and Severini, S., An example of graph limit of growing sequences of random graphs, J. Comb. 4(1) (2013), 67–80.Google Scholar
12.Kleinberg, R. D. and Kleinberg, J. M., Isomorphism and embedding problems for infinite limits of scale-free graphs, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2005, pp. 277–286 (electronic).Google Scholar
13.Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A. and Upfal, E., Stochastic models for the web graph, 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000), pp. 57–65 (IEEE Computer Society Press, Los Alamitos, CA, 2000).Google Scholar
14.Lovász, L. and Szegedy, B., Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), 933–957.Google Scholar
15.Rado, R., Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340.Google Scholar
16.Spencer, J. H., The strange logic of random graphs, Algorithms and Combinatorics, Volume 22 (Springer, 2001).Google Scholar
17.Truss, J. K., The group of the countable universal graph, Math. Proc. Cambridge Philos. Soc. 98(2) (1985), 213–245.Google Scholar
18.van der Hofstad, R., Percolation and random graphs, In New perspectives in stochastic geometry (eds Molchanov, I. S. and Kendall, W. S.), pp. 173–247 (Oxford University Press, Oxford, 2010).Google Scholar