𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Growth of components in random graphs

✍ Scribed by Svante Janson

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
134 KB
Volume
17
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Algorithmic theory of random graphs
Algorithmic theory of random graphs
✍ Alan Frieze; Colin McDiarmid πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 318 KB πŸ‘ 2 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

2-factors in random regular graphs
2-factors in random regular graphs
✍ Robalewska, Hanna D. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 474 KB πŸ‘ 2 views

In this paper the expectation and variance of the number of 2-factors in random r-regular graphs for any fixed r 2 3 is analyzed and the asymptotic distribution of this variable is determined.

1-Factorizations of random regular graph
1-Factorizations of random regular graphs
✍ M. S. O. Molloy; H. Robalewska; R. W. Robinson; N. C. Wormald πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 204 KB πŸ‘ 2 views

It is shown that for each r G 3, a random r-regular graph on 2 n vertices is equivalent in a certain sense to a set of r randomly chosen disjoint perfect matchings of the 2 n vertices, as n Βͺ Ο±. This equivalence of two sequences of probabilistic spaces, called contiguity, occurs when all events almo

On a random graph with immigrating verti
On a random graph with immigrating vertices: Emergence of the giant component
✍ David J. Aldous; Boris Pittel πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 186 KB πŸ‘ 2 views

A randomly evolving graph, with vertices immigrating at rate n and each possible edge appearing at rate 1/n, is studied. The detailed picture of emergence of giant components with O n 2/3 vertices is shown to be the same as in the ErdΕ‘s-RΓ©nyi graph process with the number of vertices fixed at n at t