Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-23T13:28:25.607Z Has data issue: false hasContentIssue false
  • English
  • Français

The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph

Published online by Cambridge University Press:  12 September 2008

Svante Janson
Svante Janson
Affiliation:
Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Swedenemail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph Gnm are shown to be asymptotically normal if m is neither too large nor too small. At the lowest limit m ≍ n3/2, these numbers are asymptotically log-normal. For Gnp, the numbers are asymptotically log-normal for a wide range of p, including p constant. The same results are obtained for random directed graphs and bipartite graphs. The results are proved using decomposition and projection methods.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 1 , March 1994 , pp. 97 - 126
Copyright
Copyright © Cambridge University Press 1994

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]Bollobás, B. (1985) Random Graphs. Academic Press, London.Google Scholar
[2]Frieze, A. and Suen, S. (1992) Counting the number of Hamilton cycles in random digraphs, Random Struct. Alg. 3, 235–241.CrossRefGoogle Scholar
[3]Janson, S. (1986) Random trees in a graph and trees in a random graph, Math. Proc. Camb. Phil. Soc. 100, 319–330.CrossRefGoogle Scholar
[4]Janson, S. (1994) Orthogonal decompositions and functional limit theorems for random graph statistics. Mem. Amer. Math. Soc. (to appear).CrossRefGoogle Scholar
[5]Jerrum, M. (1993) An analysis of a Monte Carlo algorithm for estimating the permanent. Proceedings of the 3rd conference on Integer Programming and Combinatorial Optimization, CORE, Louvain-la-Neuve, Belgium171–182.Google Scholar
[6]Moon, J. W. (1967) Enumerating labelled trees. In: Harary, F. (ed.) Graph theory and theoretical physics, Academic Press, London, 261–272.Google Scholar
[7]Ruciński, A. (1988) When are small subgraphs of a random graph normally distributed? Prob. Th. Rel. Fields. 78, 1–10.CrossRefGoogle Scholar