Random Graphs

by Janson, Svante; Luczak, Tomasz; Rucinski, Andrzej

• ISBN13: 9780471175414
• ISBN10: 0471175412
• Edition: 1st
• Format: Hardcover
• Copyright: 2000-03-13
• Publisher: Wiley-Interscience

Summary

* Ample exercises, figures, and bibliographic references

Author Biography

SVANTE JANSON, PhD, is Professor of Mathematics at Uppsala University, Sweden. <p> TOMASZ LUCZAK, PhD, is Professor of Mathematics at Adam Mickiewicz University, Poland, and a visiting professor at Emory University, Atlanta, Georgia. <p> J RUCINSKI, PhD, is Professor of Mathematics at Adam Mickiewicz University and a visiting professor at Emory University.

Table of Contents

Preface	v
Preliminaries	1	(24)
Models of random graphs	1	(5)
Notes on notation and more	6	(6)
Monotonicity	12	(2)
Asymptotic equivalence	14	(4)
Thresholds	18	(2)
Sharp thresholds	20	(5)
Exponentially Small Probabilities	25	(28)
Independent summands	26	(4)
Binomial random subsets	30	(4)
Suen's inequality	34	(3)
Martingales	37	(2)
Talagrand's inequality	39	(9)
The upper tail	48	(5)
Small Subgraphs	53	(28)
The containment problem	53	(9)
Leading overlaps and the subgraphs plot	62	(4)
Subgraph count at the threshold	66	(2)
The covring problem	68	(7)
Disjoint copies	75	(2)
Variations on the theme	77	(4)
Matchings	81	(22)
Perfect matchings	82	(7)
G-factors	89	(7)
Two open problems	96	(7)
The Phase Transition	103	(36)
The evolution of the random graph	103	(4)
The emergence of the giant component	107	(5)
The emergence of the giant: A closer look	112	(9)
The structure of the giant component	121	(5)
Near the critical period	126	(2)
Global properties and the summetry rule	128	(6)
Dynamic properties	134	(5)
Asymptotic Distributions	139	(40)
The method of modments	140	(12)
Stein's method: The Poisson case	152	(5)
Stein's method: The normal case	157	(5)
Projections and decompositions	162	(14)
Further methods	176	(3)
The Chromatic number	179	(22)
The stability number	179	(5)
The chromatic number: A greedy approach	184	(3)
The concentration of the chromatic number	187	(3)
The chromatic number of dense random graphs	190	(2)
The chromatic number of sparse random graphs	192	(4)
Vertex partition properties	196	(5)
Extremal and Ramsey Properties	201	(32)
Heuristics and results	202	(7)
Triangles: The first approach	209	(3)
The Szemeredi Regularity lemma	212	(4)
A partition theorem for random graphs	216	(6)
Triangles: An approach with perspective	222	(11)
Random Regular Graphs	233	(38)
The configuration model	235	(1)
Small cycles	236	(3)
Hamilton cycles	239	(8)
Proofs	247	(9)
Contiguity of random regular graphs	256	(8)
A brief course in contiguity	264	(7)
Zero-One Laws	271	(36)
Preliminaries	271	(2)
Ehrenfeucht games and zero-one laws	273	(12)
Filling gaps	285	(7)
Sums of models	292	(9)
Separability and the speed of convergence	301	(6)
References	307	(20)
Index of Notation	327	(4)
Index	331