Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-26T00:55:48.943Z Has data issue: false hasContentIssue false
  • English
  • Français

The probability that a random multigraph is simple. II

Part of: Graph theory Combinatorial probability

Published online by Cambridge University Press:  30 March 2016

Svante Janson
Svante Janson*
Affiliation:
Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala, Sweden. Email address: [email protected].
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.

Consider a random multigraph G* with given vertex degrees d1,…, dn, constructed by the configuration model. We give a new proof of the fact that, asymptotically for a sequence of such multigraphs with the number of edges the probability that the multigraph is simple stays away from 0 if and only if The new proof uses the method of moments, which makes it possible to use it in some applications concerning convergence in distribution. Corresponding results for bipartite graphs are included.

Keywords

Configuration modelrandom multigraphrandom bipartite graph

MSC classification

Primary: 05C80: Random graphs 05C30: Enumeration in graph theory 60C05: Combinatorial probability
Type
Part 4. Random graphs and particle systems
Information
Journal of Applied Probability , Volume 51 , Issue A: Celebrating 50 Years of The Applied Probability Trust , December 2014 , pp. 123 - 137
Copyright
Copyright © Applied Probability Trust 2014 

References

Békéssy, A., Békéssy, P. and Komlós, J. (1972). Asymptotic enumeration of regular matrices. Studia Sci. Math. Hungar. 7, 343–353.Google Scholar
Bender, E. A., and Canfield, E. R. (1978). The asymptotic number of labeled graphs with given degree sequences. J. Combinatorial Theory A 24, 296–307.Google Scholar
Blanchet, J., and Stauffer, A. (2013). Characterizing optimal sampling of binary contingency tables via the configuration model. Random Structures Algorithms 42, 159–184.Google Scholar
Bollobás, B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Europ. J. Combinatorics 1, 311–316.Google Scholar
Bollobás, B. (2001). Random Graphs, 2nd edn. Cambridge University Press.Google Scholar
Bollobás, B., and Riordan, O. (2012). An old approach to the giant component problem. Preprint. Available at http://arxiv.org/abs/1209.3691v1.Google Scholar
Flajolet, P., and Sedgewick, R. (2009). Analytic Combinatorics. Cambridge University Press.Google Scholar
Greenhill, C., McKay, B. D., and Wang, X. (2006). Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums. J. Combinatorial Theory A 113, 291–324.Google Scholar
Gut, A. (2013). Probability: A Graduate Course, 2nd edn. Springer, New York.Google Scholar
Janson, S. (2009). The probability that a random multigraph is simple. Combinatorics Prob. Comput. 18, 205–225.Google Scholar
Janson, S., and Luczak, M. J. (2008). Asymptotic normality of the k-core in random graphs. Ann. Appl. Prob. 18, 1085–1137.Google Scholar
Janson, S., Luczak, M., and Windridge, P. (2014). Law of large numbers for the SIR epidemic on a random graph with given degrees. Random Structures Algorithms 45, 724–761.Google Scholar
McKay, B. D. (1984). Asymptotics for 0-1 matrices with prescribed line sums. In Enumeration and Design (Waterloo, Ontario, 1982), Academic Press, Toronto, ON, pp. 225–238.Google Scholar
McKay, B. D. (1985). Asymptotics for symmetric 0-1 matrices with prescribed row sums. Ars Combinatoria 19A, 15–25.Google Scholar
McKay, B. D., and Wormald, N. C. (1991). Asymptotic enumeration by degree sequence of graphs with degrees o(nsp 1/2). Combinatorica 11, 369–382.CrossRefGoogle Scholar
Olver, F. W. J., Lozier, D. W., Boisvert, R. F., and Clark, C. W. (2010). NIST Handbook of Mathematical Functions. Cambridge University Press.Google Scholar
Wormald, N. C. (1978). Some problems in the enumeration of labelled graphs. , University of Newcastle.Google Scholar
Wormald, N. C. (1981). The asymptotic distribution of short cycles in random regular graphs. J. Combinatorial Theory B 31, 168–182.Google Scholar