Random trees in random graphs

Authors:
E. A. Bender and N. C. Wormald

Journal:
Proc. Amer. Math. Soc. **103** (1988), 314-320

MSC:
Primary 05C80; Secondary 05C05

DOI:
https://doi.org/10.1090/S0002-9939-1988-0938689-5

MathSciNet review:
938689

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that a random labeled -vertex graph almost surely contains isomorphic copies of almost all labeled -vertex trees, in two senses. In the first sense, the probability of each edge occurring in the graph diminishes as increases, and the set of trees referred to as "almost all" depends on the random graph. In the other sense, the probability of an edge occurring is fixed, and the relevant set of trees is predetermined. The same method applies to show that almost all labeled -tournaments contain isomorphic copies of almost all labeled oriented -trees.

**[1]**L. E. Clarke,*On Cayley’s formula for counting trees*, J. London Math. Soc.**33**(1958), 471–474. MR**0100854**, https://doi.org/10.1112/jlms/s1-33.4.471**[2]**P. Erdős and A. Rényi,*On the evolution of random graphs*, Magyar Tud. Akad. Mat. Kutató Int. Közl.**5**(1960), 17–61 (English, with Russian summary). MR**0125031****[3]**P. Erdős and A. Rényi,*On random matrices. II*, Studia Sci. Math. Hungar.**3**(1968), 459–464. MR**0244072****[4]**Paul Erdős and Joel Spencer,*Probabilistic methods in combinatorics*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974. Probability and Mathematical Statistics, Vol. 17. MR**0382007****[5]**János Komlós and Endre Szemerédi,*Limit distribution for the existence of Hamiltonian cycles in a random graph*, Discrete Math.**43**(1983), no. 1, 55–63. MR**680304**, https://doi.org/10.1016/0012-365X(83)90021-3**[6]**A. D. Korshunov,*Solution of a problem of Erdös and Rényi on Hamiltonian cycles in undirected graphs*, Soviet Math. Dokl.**17(3)**(1976), 760-764.**[7]**J. W. Moon,*On the maximum degree in a random tree*, Michigan Math. J.**15**(1968), 429–432. MR**0233729****[8]**K. B. Reid and N. C. Wormald,*Embedding oriented 𝑛-trees in tournaments*, Studia Sci. Math. Hungar.**18**(1983), no. 2-4, 377–387. MR**787942****[9]**D. Sumner, private communication with K. B. Reid.**[10]**Nicholas C. Wormald,*Subtrees of large tournaments*, Combinatorial mathematics, X (Adelaide, 1982) Lecture Notes in Math., vol. 1036, Springer, Berlin, 1983, pp. 417–419. MR**731598**, https://doi.org/10.1007/BFb0071535

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
05C80,
05C05

Retrieve articles in all journals with MSC: 05C80, 05C05

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1988-0938689-5

Article copyright:
© Copyright 1988
American Mathematical Society