Random Graphs

RANDOM GRAPHS, 2ND ED.......Page 1
Half-title......Page 2
Cambridge Studies in Advanced Mathematics......Page 3
Title Page......Page 4
Copyright Page......Page 5
Dedication......Page 6
Contents......Page 8
Preface......Page 12
Notation......Page 18
1.1 Notation and Basic Facts......Page 20
1.2 Some Basic Distributions......Page 24
1.3 Normal Approximation......Page 28
1.4 Inequalities......Page 34
1.5 Convergence in Distribution......Page 44
Exercises......Page 49
2.1 The Basic Models......Page 53
2.2 Properties of Almost All Graphs......Page 62
2.3 Large Subsets of Vertices......Page 65
2.4 Random Regular Graphs......Page 69
Exercises......Page 76
3.1 The Distribution of an Element of the Degree Sequence......Page 79
3.2 Almost Determined Degrees......Page 84
3.3 The Shape of the Degree Sequence......Page 88
3.4 Jumps and Repeated Values......Page 91
3.5 Fast Algorithms for the Graph Isomorphism Problem......Page 93
Exercises......Page 94
4 Small Subgraphs......Page 97
4.1 Strictly Balanced Graphs......Page 98
4.2 Arbitrary Subgraphs......Page 104
4.3 Poisson Approximation......Page 110
Exercises......Page 113
5.1 Trees of Given Sizes As Components......Page 115
5.2 The Number of Vertices on Tree Components......Page 121
5.3 The Largest Tree Components......Page 129
5.4 Components Containing Cycles......Page 136
Exercises......Page 147
6.1 A Gap in the Sequence of Components......Page 149
6.2 The Emergence of the Giant Component......Page 157
6.3 Small Components after Time n/2......Page 162
6.4 Further Results......Page 167
6.5 Two Applications......Page 172
Exercises......Page 177
7 Connectivity and Matchings......Page 179
7.1 The Connectedness of Random Graphs......Page 180
7.2 The k-Connectedness of Random Graphs......Page 185
7.3 Matchings in Bipartite Graphs......Page 190
7.4 Matchings in Random Graphs......Page 197
7.5 Reliable Networks......Page 208
7.6 Random Regular Graphs......Page 214
Exercises......Page 217
8 Long Paths and Cycles......Page 220
8.1 Long Paths in G c/n—First Approach......Page 221
8.2 Hamilton Cycles—First Approach......Page 225
8.3 Hamilton Cycles—Second Approach......Page 231
8.4 Long Paths in G c/n—Second Approach......Page 238
8.5 Hamilton Cycles in Regular Graphs—First Approach......Page 240
8.6 Hamilton Cycles in Regular Graphs—Second Approach......Page 243
Exercises......Page 247
9.1 The Number of Unlabelled Graphs......Page 248
9.2 The Asymptotic Number of Unlabelled Regular Graphs......Page 260
9.3 Distinguishing Vertices by Their Distance Sequences......Page 262
9.4 Asymmetric Graphs......Page 264
9.5 Graphs with a Given Automorphism Group......Page 267
Exercises......Page 268
10.1 Large Graphs of Small Diameter......Page 270
10.2 The Diameter of G p......Page 273
10.3 The Diameter of Random Regular Graphs......Page 283
10.4 Graph Processes......Page 286
10.5 Related Results......Page 290
10.6 Small Worlds......Page 295
Exercises......Page 299
11.1 Cliques in G p......Page 301
11.2 Poisson Approximation......Page 309
11.3 Greedy Colouring of Random Graphs......Page 313
11.4 The Chromatic Number of Random Graphs......Page 317
11.5 Sparse Graphs......Page 322
Exercises......Page 335
12 Ramsey Theory......Page 338
12.1 Bounds on R(s)......Page 339
12.2 Off-Diagonal Ramsey Numbers......Page 343
12.3 Triangle-Free Graphs......Page 351
12.4 Dense Subgraphs......Page 358
12.5 The Size-Ramsey Number of a Path......Page 360
Exercises......Page 364
13.1 Character Sums......Page 367
13.2 The Paley Graph P q......Page 376
13.3 Dense Graphs......Page 384
13.4 Sparse Graphs......Page 392
13.5 Pseudorandom Graphs......Page 395
Exercises......Page 400
14 Sequences, Matrices and Permutations......Page 402
14.1 Random Subgraphs of the Cube......Page 403
14.2 Random Matrices......Page 413
14.3 Balancing Families of Sets......Page 418
14.4 Random Elements of Finite Groups......Page 427
14.5 Random Mappings......Page 431
Exercises......Page 440
15 Sorting Algorithms......Page 444
15.1 Finding Most Comparisons in One Round......Page 445
15.2 Sorting in Two Rounds......Page 450
15.3 Sorting with Width n/2......Page 454
15.4 Bin Packing......Page 461
Exercises......Page 465
16.1 Connectivity......Page 466
16.2 Independent Sets......Page 467
16.3 Colouring......Page 470
16.4 Regular Graphs......Page 474
References......Page 476
Index......Page 515
Back Cover......Page 518