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.

Google Online Preview   Download