𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Random trees and random graphs

✍ Scribed by Tomasz Łuczak

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
205 KB
Volume
13
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

In the paper we study the asymptotic behavior of the number of trees with n Ž .

Ž . vertices and diameter k s k n , where n y k rnª a as n ª ϱ for some constant a-1. We use this result to determine the limit distribution of the diameter of the random graph Ž .

📜 SIMILAR VOLUMES

Random interval graphs
Random interval graphs
✍ Nicholas Pippenger 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB

We consider models for random interval graphs that are based on stochastic service systems, with vertices corresponding to customers and edges corresponding to pairs of customers that are in the system simultaneously. The number N of vertices in a connected component thus corresponds to the number o

Bisecting sparse random graphs
Bisecting sparse random graphs
✍ Malwina J. Luczak; Colin McDiarmid 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB
A family of random trees with random edg
A family of random trees with random edge lengths
✍ David Aldous; Jim Pitman 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 212 KB 👁 2 views

We introduce a family of probability distributions on the space of trees with I labeled vertices and possibly extra unlabeled vertices of degree 3, whose edges have positive real lengths. Formulas for distributions of quantities such as degree sequence, shape, and total length are derived. An interp

The largest induced tree in a sparse ran
The largest induced tree in a sparse random graph
✍ W. Fernandez de la Vega 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 2 views

The author proved that, for c > 1, the random graph G(n, p ) on n vertices with edge probability p = c / n contains almost always an induced tree on at least q n ( 1 -o( 1)) vertices, where L Y ~ is the positive root of the equation CLY = log( 1 + c'a). It is shown here that if c is sufficiently lar

Algorithmic theory of random graphs
Algorithmic theory of random graphs
✍ Alan Frieze; Colin McDiarmid 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 1 views

The theory of random graphs has been mainly concerned with structural w x properties, in particular the most likely values of various graph invariantsᎏsee Bollobas 21 . There has been increasing interest in using random graphs as models for the average case analysis of graph algorithms. In this pap