INTRODUCTION TO RANDOM GRAPHS
INTRODUCTION TO RANDOM GRAPHS
ALAN FRIEZE and MICHAL KARON? SKI October 30, 2023
To Carol and Jola
2
Contents
I Basic Models
1
1 Random Graphs
3
1.1 Models and Relationships . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Thresholds and Sharp Thresholds . . . . . . . . . . . . . . . . . . 9
1.3 Pseudo-Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 Evolution
21
2.1 Sub-Critical Phase . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Super-Critical Phase . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3 Phase Transition . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3 Vertex Degrees
51
3.1 Degrees of Sparse Random Graphs . . . . . . . . . . . . . . . . . 51
3.2 Degrees of Dense Random Graphs . . . . . . . . . . . . . . . . . 57
3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4 Connectivity
67
4.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 k-connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5 Small Subgraphs
75
5.1 Thresholds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Asymptotic Distributions . . . . . . . . . . . . . . . . . . . . . . 79
5.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
i
ii
CONTENTS
5.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6 Spanning Subgraphs
85
6.1 Perfect Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.2 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.3 Long Paths and Cycles in Sparse Random Graphs . . . . . . . . . 97
6.4 Greedy Matching Algorithm . . . . . . . . . . . . . . . . . . . . 99
6.5 Random Subgraphs of Graphs with Large Minimum Degree . . . 103
6.6 Spanning Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . 106
6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.8 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7 Extreme Characteristics
115
7.1 Diameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.2 Largest Independent Sets . . . . . . . . . . . . . . . . . . . . . . 121
7.3 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.4 Chromatic Number . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.5 Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
8 Extremal Properties
145
8.1 Containers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.2 Ramsey Properties . . . . . . . . . . . . . . . . . . . . . . . . . 146
8.3 Tura?n Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
8.4 Containers and the proof of Theorem 8.1 . . . . . . . . . . . . . . 150
8.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
8.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
9 Resilience
161
9.1 Perfect Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . 161
9.2 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 162
9.3 The chromatic number . . . . . . . . . . . . . . . . . . . . . . . 174
9.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
9.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
II Basic Model Extensions
177
10 Inhomogeneous Graphs
179
10.1 Generalized Binomial Graph . . . . . . . . . . . . . . . . . . . . 179
10.2 Expected Degree Model . . . . . . . . . . . . . . . . . . . . . . 186
CONTENTS
iii
10.3 Kronecker Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 193 10.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 10.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
11 Fixed Degree Sequence
203
11.1 Configuration Model . . . . . . . . . . . . . . . . . . . . . . . . 203
11.2 Connectivity of Regular Graphs . . . . . . . . . . . . . . . . . . 214
11.3 Existence of a giant component . . . . . . . . . . . . . . . . . . . 217
11.4 Gn,r is asymmetric . . . . . . . . . . . . . . . . . . . . . . . . . 222
11.5 Gn,r versus Gn,p . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
11.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
11.7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
12 Intersection Graphs
241
12.1 Binomial Random Intersection Graphs . . . . . . . . . . . . . . . 241
12.2 Random Geometric Graphs . . . . . . . . . . . . . . . . . . . . . 251
12.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
12.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
13 Digraphs
267
13.1 Strong Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . 267
13.2 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 275
13.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
13.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
14 Hypergraphs
281
14.1 Component Size . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
14.2 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 286
14.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
14.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
15 Thresholds
295
15.1 The Kahn-Kalai conjecture . . . . . . . . . . . . . . . . . . . . . 298
15.2 Proof of the Kahn-Kalai conjecture . . . . . . . . . . . . . . . . . 299
15.3 Constructing a cover . . . . . . . . . . . . . . . . . . . . . . . . 299
15.4 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
15.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
15.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
iv
CONTENTS
III Other models
307
16 Trees
309
16.1 Labeled Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
16.2 Recursive Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
16.3 Inhomogeneous Recursive Trees . . . . . . . . . . . . . . . . . . 326
16.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
16.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
17 Mappings
343
17.1 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
17.2 Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
17.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
17.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
18 k-out
357
18.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
18.2 Perfect Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . 360
18.3 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 369
18.4 Nearest Neighbor Graphs . . . . . . . . . . . . . . . . . . . . . . 372
18.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
18.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
19 Real World Networks
379
19.1 Preferential Attachment Graph . . . . . . . . . . . . . . . . . . . 379
19.2 Spatial Preferential Attachment . . . . . . . . . . . . . . . . . . . 387
19.3 Preferential Attachment with Deletion . . . . . . . . . . . . . . . 393
19.4 Bootstrap Percolation . . . . . . . . . . . . . . . . . . . . . . . . 401
19.5 A General Model of Web Graphs . . . . . . . . . . . . . . . . . . 402
19.6 Small World . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
19.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
19.8 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
20 Weighted Graphs
421
20.1 Minimum Spanning Tree . . . . . . . . . . . . . . . . . . . . . . 421
20.2 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
20.3 Minimum Weight Assignment . . . . . . . . . . . . . . . . . . . 428
20.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432
20.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
21 Brief notes on uncovered topics
437
CONTENTS
v
IV Tools and Methods
449
22 Moments
451
22.1 First and Second Moment Method . . . . . . . . . . . . . . . . . 451
22.2 Convergence of Moments . . . . . . . . . . . . . . . . . . . . . . 454
22.3 Stein?Chen Method . . . . . . . . . . . . . . . . . . . . . . . . . 458
23 Inequalities
461
23.1 Binomial Coefficient Approximation . . . . . . . . . . . . . . . . 461
23.2 Balls in Boxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
23.3 FKG Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
23.4 Sums of Independent Bounded Random Variables . . . . . . . . . 465
23.5 Sampling Without Replacement . . . . . . . . . . . . . . . . . . 471
23.6 Janson's Inequality . . . . . . . . . . . . . . . . . . . . . . . . . 472
23.7 Martingales. Azuma-Hoeffding Bounds . . . . . . . . . . . . . . 474
23.8 Talagrand's Inequality . . . . . . . . . . . . . . . . . . . . . . . . 481
23.9 Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
24 Differential Equations Method
487
25 Branching Processes
493
26 Entropy
495
26.1 Basic Notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
26.2 Shearer's Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 498
27 Indices
555
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
Main Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
vi
CONTENTS
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- 100 things to draw pikaland
- best practices for dot random drug and alcohol testing
- random number generation c
- simple random sampling
- modeling radioactive decay with dice
- introduction to random graphs
- random number geuerators good ones are hard to
- 06 random number generation freie universität
- sketch idea generator
Related searches
- introduction to financial management pdf
- introduction to finance
- introduction to philosophy textbook
- introduction to philosophy pdf download
- introduction to philosophy ebook
- introduction to marketing student notes
- introduction to marketing notes
- introduction to information systems pdf
- introduction to business finance pdf
- introduction to finance 15th edition
- introduction to finance books
- introduction to finance online course