INTRODUCTION TO RANDOM GRAPHS - CMU

1 INTRODUCTION TO RANDOM GRAPHSALAN FRIEZE and MICHA KARO NSKID ecember 3, 2022To Carol and Jola2 ContentsI Basic Models11 RANDOM and Relationships .. and Sharp Thresholds .. 192 Phase .. Phase .. Transition .. 483 Vertex of Sparse RANDOM GRAPHS .. of Dense RANDOM GRAPHS .. 644 .. 745 Small .. Distributions .. 836 Spanning Matchings .. Cycles .. Paths and Cycles in Sparse RANDOM GRAPHS .. Matching Algorithm .. Subgraphs of GRAPHS with Large Minimum Degree .. Subgraphs .. 1117 Extreme .. Independent Sets .. Number .. 1418 Extremal .. Properties .. an Properties .. and the proof of Theorem .. 1589 Matchings .. Cycles .. chromatic number .. 175II Basic Model Extensions17710 Inhomogeneous Generalized Binomial graph .

2 Expected Degree Model .. Kronecker GRAPHS .. Exercises .. Notes .. 19911 Fixed Degree Configuration Model .. Connectivity of Regular GRAPHS .. Existence of a giant component .. ,ris asymmetric .. ,rversusGn,p.. Exercises .. Notes .. 23812 Intersection Binomial RANDOM Intersection GRAPHS .. RANDOM Geometric GRAPHS .. Exercises .. Notes .. 26113 Strong Connectivity .. Hamilton Cycles .. Exercises .. Notes .. 27914 Component Size .. Hamilton Cycles .. Exercises .. Notes .. 29215 The Kahn-Kalai conjecture .. Proof of the Kahn-Kalai conjecture .. Constructing a cover .. Iteration .. Exercises .. Notes .. 306ivCONTENTSIII Other models30716 Labeled Trees .. Recursive Trees.

3 Inhomogeneous Recursive Trees .. Exercises .. Notes .. 33717 Permutations .. Mappings .. Exercises .. Notes .. Connectivity .. Perfect Matchings .. Hamilton Cycles .. Nearest Neighbor GRAPHS .. Exercises .. Notes .. 37619 Real World Preferential Attachment graph .. Spatial Preferential Attachment .. Preferential Attachment with Deletion .. Bootstrap Percolation .. A General Model of Web GRAPHS .. Small World .. Exercises .. Notes .. 41820 Weighted Minimum Spanning Tree .. Shortest Paths .. Minimum Weight Assignment .. Exercises .. Notes .. 43421 Brief notes on uncovered topics437 CONTENTSvIV Tools and Methods44922 First and Second Moment Method .. Convergence of Moments.

4 Stein Chen Method .. 45823 Binomial Coefficient Approximation .. Balls in Boxes .. FKG Inequality .. Sums of Independent Bounded RANDOM Variables .. Sampling Without Replacement .. Janson s Inequality .. Martingales. Azuma-Hoeffding Bounds .. Talagrand s Inequality .. Dominance .. 48424 Differential Equations Method48725 Branching Processes49326 Basic Notions .. Shearer s Lemma .. 49827 Indices555 Author Index .. 556 Main Index .. 563viCONTENTSP refaceOur purpose in writing this book is to provide a gentle INTRODUCTION to a subjectthat is enjoying a surge in interest. We believe that the subject is fascinating in itsown right, but the increase in interest can be attributed to several factors. One fac-tor is the realization that networks are everywhere.

5 From social networks suchas Facebook, the World Wide Web and the internet to the complex interactionsbetween proteins in the cells of our bodies, we face the challenge of understand-ing their structure and development. By and large natural networks grow in anunpredictable manner and this is often modeled by a RANDOM construction. An-other factor is the realization by Computer Scientists that NP-hard problems areoften easier to solve than their worst-case suggests and that an analysis of runningtimes on RANDOM instances can be GRAPHS were used by Erd os [286] to give a probabilistic construction ofa graph with large girth and large chromatic number. It was only later that Erd osand R enyi began a systematic study of RANDOM GRAPHS as objects of interest in theirown right. Early on they defined the RANDOM graphGn,mand founded the neglected in this story is the contribution of Gilbert [383] who introducedthe modelGn,p, but clearly the credit for getting the subject off the ground goes toErd os and R enyi.

6 Their seminal series of papers [287], [289], [290], [291] and inparticular [288], on the evolution of RANDOM GRAPHS laid the groundwork for othermathematicians to become involved in studying properties of RANDOM the early eighties the subject was beginning to blossom and it received aboost from two sources. First was the publication of the landmark book of B elaBollob as [136] on RANDOM GRAPHS . Around the same time, the Discrete Mathemat-ics group in Adam Mickiewicz University began a series of conferences in series continues biennially to this day and is now a conference attractingmore and more next important event in the subject was the start of the journal RandomStructures and Algorithms in 1990 followed by Combinatorics, Probability andviiviiiCONTENTSC omputing a few years later. These journals provided a dedicated outlet for workin the area and are flourishing of the bookWe have divided the book into four parts.

7 Part one is devoted to giving a detaileddescription of the main properties ofGn,mandGn,p. The aim is not to give bestpossible results, but instead to give some idea of the tools and techniques used inthe subject, as well to display some of the basic results of the area. There is suffi-cient material in part one for a one semester course at the advanced undergraduateor beginning graduate level. Once one has finished the content of the first part,one is equipped to continue with material of the remainder of the book, as well asto tackle some of the advanced monographs such as Bollob as [136] and the morerecent one by Janson, uczak and Ruci nski [450].Each chapter comes with a few exercises. Some are fairly simple and these aredesigned to give the reader practice with making some the estimations that are soprevalent in the subject.

8 In addition each chapter ends with some notes that leadthrough references to some of the more advanced important results that have notbeen two deals with models of RANDOM GRAPHS that naturally extendGn,mandGn,p. Part three deals with other models. Finally, in part four, we describe someof the main tools used in the area along with proofs of their read this book, the reader should be in a good position to pursue re-search in the area and we hope that this book will appeal to anyone interested inCombinatorics or Applied Probability or Theoretical Computer people have helped with the writing of this book and we would like toacknowledge their help. First there are the students who have sat in on coursesbased on early versions of this book and who helped to iron out the many typo would next like to thank the following people for reading parts of the bookbefore final submission.

9 Andrew Beveridge, Deepak Bal, Malgosia Bednarska,Patrick Bennett, Mindaugas Blozneliz, Antony Bonato, Boris Bukh, Fan Chung,Amin Coja-Oghlan, Colin Cooper, Andrzej Dudek, Asaf Ferber, Nikolas Foun-toulakis, Catherine Greenhill, Dan Hefetz, Paul Horn, Hsien Kuei Hwang, TalHershko, Jerzy Jaworski, Tony Johansson, Mihyun Kang, Michael Krivelevich,Tomasz uczak, Colin McDiarmid, Andrew McDowell, Hosam Mahmoud, MikeCONTENTSixMolloy, Tobias M uller, Rajko Nenadov, Wesley Pegden, Boris Pittel, Dan Poole,Pawel Pra at, Oliver Riordan, Andrzej Ruci nski, Katarzyna Rybarczyk, WojtekSamotij, Yilun Shang, Matas Silekis, Greg Sorkin, Joel Spencer, Sam Spiro, Dud-ley Stark, Angelika Steger, Prasad Tetali, Andrew Thomason, Linnus W astlund,Nick Wormald, Stephen also to B ela Bollob as for his advice on the structure of the in what follows, we will give an expression for a large positive integer.

10 Itmight not be obvious that the expression is actually an integer. In which case, thereader can rest assured that he/she can round up or down and obtained any requiredproperty. We avoid this rounding for convenience and for notational addition we list the following notation:Mathematical Relations f(x) =O(g(x)):|f(x)| K|g(x)|for some constantK>0 and allx R. f(x) = (g(x)):f(n) =O(g(x))andg(x) =O(f(x)). f(x) =o(g(x))asx a:f(x)/g(x) 0 asx a. A B:A/B 0 asn . A B:A/B asn . A B:A/B 1 as some parameter converges to 0 or or another limit. A BorB AifA (1+o(1))B. [n]: This is{1,2, .. ,n}. In general, ifa<bare positive integers, then[a,b] ={a,a+1, .. ,b}. IfSis a set andkis a non-negative integer then Sk denotes the set ofk-element subsets ofS. In particular, [n]k dnotes the set ofk-sets of{1,2, .. ,n}.Furthermore, S k =Skj=0 Sj.