Advertisement
Published in:
2001 | OriginalPaper | Chapter
Very Sparse Graphs
Author : Joel Spencer
Published in: The Strange Logic of Random Graphs
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We hold to the view proposed in the original papers of Erdös and Rényi that the random graph G(n, p) evolves as p increases from empty to full. In its early stages — much like natural evolution — the behaviors are relatively simple to describe. For the random graph, early stages means up to p ͠ 1/n. As we are viewing the random graph through only a first order lens we shall actually go a bit further in this section. We summarize the results of Section 3.1 – 3.5 with Theorem 3.0.8.