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 Free Access

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 (20:7282)****[2]**P. Erdös and A. Rényi,*On the evolution of random graphs*, Publ. Math. Inst. Hungar. Acad. Sci.**5**(1960), 17-61. MR**0125031 (23:A2338)****[3]**-,*On random matrices*. II, Studia Sci. Math. Hungar.**3**(1968), 459-464. MR**0244072 (39:5389)****[4]**P. Erdös and J. Spencer,*Probabilistic methods in combinatorics*, Academic Press, New York, 1974. MR**0382007 (52:2895)****[5]**J. Komlós and E. Szemerédi,*Limit distribution for the existence of Hamiltonian cycles in a random graph*, Discrete Math.**43**(1983), 55-63. MR**680304 (85g:05124)****[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 (38:2050)****[8]**K. B. Reid and N. C. Wormald,*Embedding oriented**-trees in tournaments*, Studia Sci. Math. Hungar.**18**(1983), 377-387. MR**787942 (86i:05075)****[9]**D. Sumner, private communication with K. B. Reid.**[10]**N. C. Wormald,*Subtrees of large tournaments*, Combinatorial Mathematics X, Lecture Notes in Math., Vol. 1036, Springer-Verlag, 1983, pp. 417-419. MR**731598 (85j:05024)**

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