## Lecture 8. Games on random graphs (2)

The last part of this lec­ture will take place on Mon­day, May 6 at 3 PM in Bend­heim Class­room 103. The full scribe notes for this lec­ture will be posted some­time after that date.

03. May 2013 by Ramon van Handel

## Lecture 7. Games on random graphs (1)

The next two lec­tures by Rene Car­mona will be on games on ran­dom graphs.
Many thanks to Patrick Rebes­chini for scrib­ing these lectures!

In the fol­low­ing we dis­cuss some results from the paper “Con­nec­tiv­ity and equi­lib­rium in ran­dom games” by Daskalakis, Dimakis, and Mos­sel. We define a ran­dom game on a ran­dom graph and we char­ac­ter­ize the graphs that are likely to exhibit Nash equi­lib­ria for this game. We show that if the ran­dom graph is drawn from the Erdös-Rényi dis­tri­b­u­tion, then in the high con­nec­tiv­ity regime the law of the num­ber of pure Nash equi­lib­ria con­verges toward a Pois­son dis­tri­b­u­tion, asymp­tot­i­cally, as the size of the graph is increased.

Let be a sim­ple (that is, undi­rected and with no self-edges) graph, and for each denote by the set of neigh­bors of , that is, . We think of each ver­tex in as a player in the game that we are about to intro­duce. At the same time, we think of each edge as a strate­gic inter­ac­tion between play­ers and .

Def­i­n­i­tion (Game on a graph). For each let rep­re­sent the set of strate­gies for player , assumed to be a finite set. We nat­u­rally extend this def­i­n­i­tion to include fam­i­lies of play­ers: for each , let be the set of strate­gies for each player in . For each , denote by the reward func­tion for player . A game is a col­lec­tion .

The above def­i­n­i­tion describes a game that is sta­tic, in the sense that the game is played only once, and local, in the sense that the reward func­tion of each player depends only on its own strat­egy and on the strat­egy of the play­ers in its neigh­bors. We now intro­duce the notion of pure Nash equilibrium.

Def­i­n­i­tion (Pure Nash equi­lib­rium). We say that is a pure Nash equi­lib­rium (PNE) if for each we have

A pure Nash equi­lib­rium rep­re­sents a state where no player can be bet­ter off by chang­ing his own strat­egy if he is the only one who is allowed to do so. In order to inves­ti­gate the exis­tence of a pure Nash equi­lib­rium it suf­fices to study the best response func­tion defined below.

Def­i­n­i­tion (Best response func­tion). Given a reward func­tion for player , we define the best response func­tion for as

Clearly, is a pure Nash equi­lib­rium if and only if for each . We now define the type of ran­dom games that we will be inter­ested in; in order to do so, we need to spec­ify the set of strate­gies and the reward func­tion for each player.

Def­i­n­i­tion (Ran­dom game on a fixed graph). For a graph and an atom­less prob­a­bil­ity mea­sure on , let be the asso­ci­ated ran­dom game defined as follows:

1. for each ;
2. is a col­lec­tion of inde­pen­dent iden­ti­cally dis­trib­uted ran­dom vari­ables with dis­tri­b­u­tion .

Remark. For each game the fam­ily is a col­lec­tion of inde­pen­dent ran­dom vari­ables that are uni­formly dis­trib­uted in , and for each , we have almost surely. In fact, note that if and only if and this event has prob­a­bil­ity since the two ran­dom vari­ables appear­ing on both sides of the inequal­ity sign are inde­pen­dent with the same law and is atom­less. As far as the analy­sis of the exis­tence of pure Nash equi­lib­ria is con­cerned, we could take the present notion of best response func­tions as the def­i­n­i­tion of our ran­dom game on a fix graph. In fact, note that the choice of in does not play a role in our analy­sis, and we would obtain the same results by choos­ing dif­fer­ent (atom­less) dis­tri­b­u­tions for sam­pling (inde­pen­dently) the reward func­tion of each player.

Denote by the dis­tri­b­u­tion of a Erdös-Rényi ran­dom graph with ver­tices where each edge is present inde­pen­dently with prob­a­bil­ity . We now intro­duce the notion of a ran­dom game on a ran­dom graph.

Def­i­n­i­tion (Ran­dom game on a ramon graph). For each , and each prob­a­bil­ity mea­sure on , do the following:

1. choose a graph from ;
2. choose a ran­dom game from for the graph .

Hence­forth, given a ran­dom vari­able let rep­re­sent its dis­tri­b­u­tion. Given two mea­sures and on a mea­sur­able space, define the total vari­a­tion dis­tance between and as

where the supre­mum is taken over mea­sur­able func­tions such that the supre­mum norm is less than or equal to .

We are now ready to state the main the­o­rem that we will prove in the fol­low­ing (The­o­rem 1.9 in Daskalakis, Dimakis, and Mos­sel).

The­o­rem 1 (High con­nec­tiv­ity regime). Let be the num­ber of pure Nash equi­lib­ria in the ran­dom game on ran­dom graph defined above. Let define the high-connectivity regime as

where sat­is­fies the fol­low­ing two properties:

Then, we have

where denotes the con­di­tional prob­a­bil­ity given the graph and is a Pois­son ran­dom vari­able with mean . In particular,

which shows that in this regime a pure Nash equi­lib­rium exists with prob­a­bil­ity con­verg­ing to as the size of the net­work increases.

Remark. Using the ter­mi­nol­ogy of sta­tis­ti­cal mechan­ics, the first result in The­o­rem 1 rep­re­sents a quenched–type result since it involves the con­di­tional dis­tri­b­u­tion of a sys­tem (i.e., the game) given its envi­ron­ment (i.e., the graph). On the other hand, the sec­ond result rep­re­sents an annealed–type result, where the uncon­di­tional prob­a­bil­ity is considered.

In order to prove The­o­rem 1 we need the fol­low­ing lemma on Pois­son approx­i­ma­tions. The lemma is adapted from the results of R. Arra­tia, L. Gold­stein, and L. Gor­don (“Two moments suf­fice for Pois­son approx­i­ma­tions: the Chen-Stein method”, Ann. Probab. 17, 9–25, 1989) and it shows how the total vari­a­tion dis­tance between the law of a sum of Bernoulli ran­dom vari­ables and a Pois­son dis­tri­b­u­tion can be bounded by the first and sec­ond moments of the Bernoulli ran­dom vari­ables. This result is a par­tic­u­lar instance of the Stein’s method in prob­a­bil­ity theory.

Lemma (Arra­tia, Gold­stein, and Gor­don, 1989). Let be a col­lec­tion of Bernoulli ran­dom vari­ables with . For each let be such that is inde­pen­dent of . Define

where . Define and . If is a Pois­son ran­dom vari­able with mean , then

Proof. We define the fol­low­ing oper­a­tors that act on each func­tion :

We point out that char­ac­ter­izes in the sense that if and only if is a Pois­son ran­dom vari­able with mean ; is an exam­ple of Stein’s oper­a­tor. First of all, we show that for each we have . In fact, if we have

and if we have

For each define and . The fol­low­ing prop­er­ties hold:

1. ,
2. ,
3. .

In what fol­lows, con­sider any given func­tion such that . Define the func­tion as for each , and let . From what was seen above we have and we get

The first term is bounded above by while the third term is equal to since is inde­pen­dent of . In order to bound the sec­ond term we want to rewrite each term as a tele­scop­ing sum. In what fol­low fix , label the ele­ments of as and define

Notic­ing that , we have

and we get

There­fore, com­bin­ing all together we get

To be continued…

01. May 2013 by Ramon van Handel

## Giant component: final remarks

The past three lec­tures were devoted to the giant com­po­nent theorem:

The­o­rem Let be the con­nected com­po­nent of that con­tains .

1. If , then in probability.
2. If , then in prob­a­bil­ity, for some .
3. If , then in distribution.

We proved only the first (sub­crit­i­cal) and sec­ond (super­crit­i­cal) cases: our pre­sen­ta­tion was largely inspired by the treat­ment of Jan­son, Luczak, and Rucin­ski and Dur­rett. We have omit­ted the crit­i­cal case, how­ever, as the last two lec­tures of the semes­ter will be on another topic. The goal of this post is to pro­vide some final remarks and ref­er­ences on the giant com­po­nent theorem.

Ret­ro­spec­tive

At first sight, the “dou­ble jump” in the giant com­po­nent the­o­rem looks quite shock­ing. In hind­sight, how­ever, this does not seem quite so mirac­u­lous, as it mir­rors an ele­men­tary phe­nom­e­non that is cov­ered in many intro­duc­tory prob­a­bil­ity courses: given a (nice) ran­dom walk with ini­tial con­di­tion , define the hit­ting time for some . Then there are three cases:

1. If has neg­a­tive drift, then . In fact, the ran­dom vari­able has a light (expo­nen­tial) tail.
2. If has pos­i­tive drift, then .
3. If has zero drift, then a.s. but . That is, the ran­dom vari­able has a heavy tail.

This “dou­ble jump” in the behav­ior of the hit­ting prob­a­bil­i­ties of a ran­dom walk is directly anal­o­gous to the behav­ior of the con­nected com­po­nents of an Erdös-Rényi graph, and this was indeed the basic idea behind the proofs given in the pre­vi­ous lec­tures. Of course, it remains a bit of a mir­a­cle that the ran­dom walk approx­i­ma­tion of the explo­ration process, which only holds for small times, is suf­fi­ciently pow­er­ful that it describes so com­pletely the behav­ior of the ran­dom graph.

The crit­i­cal case

In the sub­crit­i­cal case, the size of the largest com­po­nent is of order because the hit­ting time of a ran­dom walk with neg­a­tive drift has an expo­nen­tial tail: that is, we proved

which goes to zero as for .

Sim­i­larly, we would expect that we can obtain the size of the largest com­po­nent in the crit­i­cal case if we under­stand the heavy tail behav­ior of the hit­ting time of a ran­dom walk with zero drift. This is in fact the case. Indeed, when there is zero drift, one can show that

The crude union bound argu­ment used above now does not give the cor­rect answer, but an only slightly bet­ter argu­ment is needed. Indeed, note that

There­fore, . With some fur­ther work, a cor­re­spond­ing lower bound can also be proved. See the paper by Nach­mias and Peres or the notes by van der Hof­s­tad for the details.

It turns out that in the crit­i­cal case is not only bounded in prob­a­bil­ity, but in fact con­verges weakly to some lim­it­ing dis­tri­b­u­tion. This dis­tri­b­u­tion, and much more, is beau­ti­fully described by Aldous in terms of Brown­ian excur­sions. This is an inter­est­ing exam­ple of the appli­ca­tion of sto­chas­tic analy­sis to dis­crete prob­a­bil­ity; unfor­tu­nately, we do not have the time to cover it.

In a dif­fer­ent direc­tion, it turns out that var­i­ous addi­tional phase tran­si­tions appear when we con­sider a finer scal­ing, for exam­ple, in the “crit­i­cal win­dow” . For an overview of the var­i­ous tran­si­tions, see, for exam­ple, sec­tion 11.1 in Alon and Spencer.

Con­nec­tiv­ity threshold

Rather than con­sid­er­ing the size of the largest com­po­nent, one could ask when the entire Erdös-Rényi graph is con­nected. Note that when , the con­stant in the size of the giant com­po­nent is always strictly pos­i­tive, so the graph is not con­nected. There­fore, in order for the entire graph to be con­nected, we must let (that is, the edge prob­a­bil­ity must be super­lin­ear). It turns out that the appro­pri­ate scal­ing for this ques­tion is , and another phase tran­si­tion arises here.

The­o­rem. Let . If , then the Erdös-Rényi graph is con­nected with prob­a­bil­ity tend­ing to as . If , the graph is con­nected with prob­a­bil­ity tend­ing to as .

To get some intu­ition, con­sider the prob­a­bil­ity that a ver­tex is iso­lated (that is, dis­con­nected from every other vertex):

Thus for , we have

In par­tic­u­lar, if , then there must exist an iso­lated ver­tex with pos­i­tive prob­a­bil­ity as , in which case the graph is not con­nected (in fact, it is not hard to show that the vari­ance of the num­ber of iso­lated com­po­nents is of the same order as its mean, so that the prob­a­bil­ity that the graph is con­nected tends to zero). Some­what mirac­u­lously, it turns out that when there are no iso­lated ver­tices, then the graph must already be con­nected, so that we do indeed obtain the sharp tran­si­tion described in the The­o­rem above. For a proof of this fact (by a clever com­bi­na­to­r­ial argu­ment) see, for exam­ple, the lec­ture notes by van der Hof­s­tad. Alter­na­tively, one can use a ran­dom walk argu­ment entirely in the spirit of the proofs in the pre­vi­ous lec­tures to prove that the ran­dom graph is con­nected for : by run­ning simul­ta­ne­ous explo­ration processes from dif­fer­ent ver­tices as we did in the proof of the super­crit­i­cal case, one can show that all con­nected com­po­nents must inter­sect when and thus the entire graph must be con­nected. See sec­tion 2.8 in Dur­rett for such an argument.

28. April 2013 by Ramon van Handel

## Lecture 6. Giant component (3)

Let us begin with a brief recap from the pre­vi­ous lec­ture. We con­sider the Erdös-Rényi ran­dom graph in the super­crit­i­cal case . Recall that denotes the con­nected com­po­nent of the graph that con­tains the ver­tex . Our goal is to prove the exis­tence of the giant com­po­nent with size , while the remain­ing com­po­nents have size .

Fix suf­fi­ciently large (to be cho­sen in the proof), and define the set

of ver­tices con­tained in “large” com­po­nents. The proof con­sists of two parts:

• Part 1:
• Part 2: in probability.

Part 1 states that all the suf­fi­ciently large com­po­nents must inter­sect, form­ing the giant com­po­nent. Part 2 counts the num­ber of ver­tices in the giant com­po­nent. Part 2 was proved in the pre­vi­ous lec­ture. The goal of this lec­ture is to prove Part 1, which com­pletes the proof of the giant component.

Overview

As in the pre­vi­ous lec­tures, the cen­tral idea in the study of the giant com­po­nent is the explo­ration process , where

We have seen that , where is a ran­dom walk with increments

When , we have . Thus is approx­i­mately a ran­dom walk with pos­i­tive drift. The intu­itive idea behind the proof of Part 1 is as fol­lows. Ini­tially, the ran­dom walk can hit rapidly, in which case the com­po­nent is small. How­ever, if the ran­dom walk drifts away from zero, then with high prob­a­bil­ity it will never hit zero, in which case the com­po­nent must keep grow­ing until the ran­dom walk approx­i­ma­tion is no longer accu­rate. Thus there do not exist any com­po­nents of inter­me­di­ate size: each com­po­nent is either very small () or very large (we will show , but the pre­cise expo­nent is not important).

We now want to argue that any pair of large com­po­nents must nec­es­sar­ily inter­sect. Con­sider two dis­joint sets and of ver­tices of size . As each edge is present in the graph with prob­a­bil­ity , the prob­a­bil­ity that there is no edge between and is

We there­fore expect that any pair of large com­po­nents must inter­sect with high prob­a­bil­ity. The prob­lem with this argu­ment is that we assumed that the sets and are non­ran­dom, while the ran­dom sets them­selves depend on the edge struc­ture of the ran­dom graph (so the events and are highly cor­re­lated). To actu­ally imple­ment this idea, we there­fore need a lit­tle bit more sophis­ti­cated approach.

To make the proof work, we revisit more care­fully our ear­lier ran­dom walk argu­ment. The process has pos­i­tive drift as . Thus the process is still approx­i­mately a ran­dom walk with pos­i­tive drift! Apply­ing the above intu­ition, either dies rapidly (the com­po­nent is small), or grows lin­early in as is illus­trated in the fol­low­ing figure:

This means that the explo­ration process for a com­po­nent of size will not only grow large () with high prob­a­bil­ity, but that the explo­ration process will also pos­sess a large num­ber of active ver­tices (. To prove that all large com­po­nents inter­sect, we will run dif­fer­ent explo­ration processes simul­ta­ne­ously start­ing from dif­fer­ent ver­tices. We will show that if two of these processes reach a large num­ber of active ver­tices then there must be an edge between them with high prob­a­bil­ity, and thus the cor­re­spond­ing com­po­nents must coin­cide. This resolves the depen­dence prob­lem in our naive argu­ment, as the edges between the sets of active ver­tices have not yet been explored and are there­fore inde­pen­dent of the his­tory of the explo­ration process.

The com­po­nent size dichotomy

We now begin the proof in earnest. We will first show the dichotomy between large and small com­po­nents: either the com­po­nent size is , or the num­ber of active ver­tices grows lin­early up to time . To be pre­cise, we con­sider the fol­low­ing event:

Our goal is to show that is large.

Define the stop­ping time

We can write

Now sup­pose and . Then , as explo­ration process is alive at time and stays alive until time . We can there­fore write

To bound the prob­a­bil­i­ties inside the sum, we com­pare to a suit­able ran­dom walk.

The ran­dom walk argument

To bound the prob­a­bil­ity that , we must intro­duce a com­par­i­son ran­dom walk that lies beneath . We use the same con­struc­tion as was used in the pre­vi­ous lec­ture. Let

where , are i.i.d. ran­dom vari­ables inde­pen­dent of , (the same used in the explo­ration process), and is the set of the first com­po­nents of (if , then and thus is unde­fined; then we sim­ply add vari­ables ).

As in the pre­vi­ous lec­ture, we have:

• is a ran­dom walk with increments.
• when­ever and .

Now sup­pose that and . Then

We there­fore obtain for

Thus com­put­ing reduces to com­pute the tail prob­a­bil­ity of a ran­dom walk (or, in less fancy terms, a sum of i.i.d. ran­dom vari­ables). That is some­thing we know how to do.

Lemma (Cher­noff bound). Let . Then

Proof. Let . Then

The result fol­lows by opti­miz­ing over .

Note that . We there­fore have by the Cher­noff bound

for all (here depends only on and ). In par­tic­u­lar, we have

pro­vided is suf­fi­ciently large. Thus we can estimate

which goes to zero as pro­vided that is cho­sen suf­fi­ciently large. In par­tic­u­lar, the com­po­nent size dichotomy fol­lows: choos­ing any , we obtain

Remark: Unlike in the proof of Part 2 in the pre­vi­ous lec­ture, here we do need to choose suf­fi­ciently large for the proof to work. If is too small, then the ran­dom walk can­not move suf­fi­ciently far away from zero to ensure that it will never return. In par­tic­u­lar, even in the super­crit­i­cal case, the sec­ond largest com­po­nent has size of order .

Large com­po­nents must intersect

To com­plete the proof, it remains to show that all large com­po­nents must inter­sect. To do this, we will run sev­eral explo­ration processes at once start­ing from dif­fer­ent ver­tices. If the sets of active ver­tices of two of these processes grow large, then there must be an edge between them with high prob­a­bil­ity, and thus the cor­re­spond­ing com­po­nents inter­sect. Let us make this argu­ment precise.

In the fol­low­ing, we denote by the explo­ration process started at . For each such process, we define the cor­re­spond­ing set that we have inves­ti­gated above:

We have shown above that, pro­vided , we have

We can there­fore estimate

Now note that by time , the explo­ration process has only explored edges where (or ), and sim­i­larly for . It fol­lows that

In par­tic­u­lar, if are dis­joint sub­sets of ver­tices, then

On the other hand, implies that must be dis­joint at every time . Thus if , there can be no edges between ver­tices in and at any time (if such an edge exists, then the ver­tices con­nected by this edge will even­tu­ally be explored by both explo­ration processes, and then the sets of removed ver­tices will no longer be dis­joint). Therefore,

Thus we finally obtain

and the proof of the giant com­po­nent the­o­rem is complete.

Many thanks to Quentin Berthet for scrib­ing this lecture!

27. April 2013 by Ramon van Handel

## Lecture 5. Giant component (2)

Con­sider the Erdös-Rényi graph model , and denote as usual by the con­nected com­po­nent of the graph that con­tains the ver­tex . In the last lec­ture, we focused mostly on the sub­crit­i­cal case , where we showed that . Today we will begin devel­op­ing the super­crit­i­cal case , where for a suit­able con­stant . In par­tic­u­lar, our aim for this and next lec­ture is to prove the fol­low­ing theorem.

The­o­rem. Let . Then

where is the small­est pos­i­tive solu­tion of the equa­tion . More­over, there is a such that all but one of the com­po­nents have size with prob­a­bil­ity tend­ing to as .

Begin­ning of the proof. Define the set

The proof of the The­o­rem con­sists of two main parts:

• Part 1: .
• Part 2: in probability.

Part 1 states that all “large” com­po­nents of the graph must inter­sect, form­ing one giant com­po­nent. Some intu­ition for why this is the case was given at the end of the pre­vi­ous lec­ture. Part 2 com­putes the size of this giant com­po­nent. In this lec­ture, we will con­cen­trate on prov­ing Part 2, and we will find out where the mys­te­ri­ous con­stant comes from. In the next lec­ture, we will prove Part 1, and we will develop a detailed under­stand­ing of why all large com­po­nents must intersect.

Before we pro­ceed, let us com­plete the proof of the The­o­rem assum­ing Parts 1 and 2 have been proved. First, note that with prob­a­bil­ity tend­ing to one, the set is itself a con­nected com­po­nent. Indeed, if and then must lie in dis­joint con­nected com­po­nents by the def­i­n­i­tion of . On the other hand, with prob­a­bil­ity tend­ing to one, all must lie in the same con­nected com­po­nent by Part 1. There­fore, with prob­a­bil­ity tend­ing to one, the set forms a sin­gle con­nected com­po­nent of the graph. By Part 2, the size of this com­po­nent is , while by the def­i­n­i­tion of , all other com­po­nents have size . This com­pletes the proof.

The remain­der of this lec­ture is devoted to prov­ing Part 2 above. We will first prove that the claim holds on aver­age, and then prove con­cen­tra­tion around the aver­age. More pre­cisely, we will show:

1. .
2. .

Together, these two claims evi­dently prove Part 2.

Mean size of the giant component

We begin by writ­ing out the mean size of the giant component:

where we note that does not depend on the ver­tex by the sym­me­try of the Erdös-Rényi model. There­fore, to prove con­ver­gence of the mean size of the giant com­po­nent, it suf­fices to prove that

This is what we will now set out to accomplish.

In the pre­vi­ous lec­ture we defined explo­ration process . We showed that

and that for

where is an arbi­trary nonan­tic­i­pat­ing choice, say, (recall that denotes the adja­cency matrix of the ran­dom graph). As are i.i.d. and as edges ema­nat­ing from the set of unex­plored ver­tices have not yet appeared in pre­vi­ous steps, the process is “almost” a ran­dom walk: it fails to be a ran­dom walk as we only add Bernoulli vari­ables in each iter­a­tion, rather than a con­stant num­ber. In the last lec­ture, we noted that we can esti­mate from above by a gen­uine ran­dom walk by adding some fic­ti­tious ver­tices. To be pre­cise, we define

where are i.i.d. inde­pen­dent of the (if , then and thus is unde­fined; in this case, we sim­ply add all vari­ables ). In the present lec­ture, we also need to bound from below. To this end, we intro­duce another process as follows:

where is the set con­sist­ing of the first ele­ments of in increas­ing order of the ver­tices (if , we add vari­ables ). The idea behind these processes is that is engi­neered, by includ­ing “fic­ti­tious” ver­tices, to always add i.i.d. Bernoulli vari­ables in every iter­a­tion, while is engi­neered, by includ­ing “fic­ti­tious” ver­tices when is small and omit­ting ver­tices when is large, to always add i.i.d. Bernoulli vari­ables in every iter­a­tion. The fol­low­ing facts are immediate:

• is a ran­dom walk with i.i.d. increments.
• is a ran­dom walk with i.i.d. increments.
• for all .
• for all on the event .

To see the last prop­erty, note that the explo­ration process can only explore as many ver­tices as are present in the con­nected com­po­nent , so that for all ; there­fore, in this sit­u­a­tion only the sec­ond pos­si­bil­ity in the def­i­n­i­tion of occurs, and it is obvi­ous by con­struc­tion that then (nonethe­less, the first pos­si­bil­ity in the def­i­n­i­tion must be included to ensure that is a ran­dom walk).

We now define the hit­ting times

Then we evi­dently have

(Note how we clev­erly chose the ran­dom walk pre­cisely so that when­ever ). We have there­fore reduced the prob­lem of com­put­ing to com­put­ing the hit­ting prob­a­bil­i­ties of ran­dom walks. Now we are in busi­ness, as this is some­thing we know how to do using martingales!

The hit­ting time computation

Let us take a moment to gather some intu­ition. The ran­dom walks and have incre­ments dis­trib­uted as and , respec­tively. As , both incre­ment dis­tri­b­u­tions con­verge to a dis­tri­b­u­tion, so we expect that where is the first hit­ting time of the Pois­son ran­dom walk. On the other hand, as , we expect that . The prob­lem then reduces to com­put­ing the prob­a­bil­ity that a Pois­son ran­dom walk ever hits the ori­gin. This com­pu­ta­tion can be done explic­itly, and this is pre­cisely where the mys­te­ri­ous con­stant comes from!

We now pro­ceed to make this intu­ition pre­cise. First, we show that the prob­a­bil­ity can indeed be replaced by , as one might expect.

Lemma. as .

Proof. We need to show that

Note that as when ,

We can evi­dently write

where and

Choos­ing , we obtain for . There­fore,

This com­pletes the proof.

By the above Lemma, and a triv­ial upper bound, we obtain

To com­plete com­pu­ta­tion of the mean size of the giant com­po­nent, it there­fore remains to show that and con­verge to . In fact, we can com­pute these quan­ti­ties exactly.

Lemma. Let . Then

where is the small­est pos­i­tive solu­tion of .

Proof. Recall the mar­tin­gale used in last lecture:

Sup­pose that and . Then

The first equal­ity holds since if then and , while if then and . The sec­ond equal­ity holds by dom­i­nated con­ver­gence since , and the third equal­ity is by the optional stop­ping theorem.

Now sup­pose we can find such that as . Then we have

by dom­i­nated con­ver­gence. Thus, evi­dently, it suf­fices to find with the req­ui­site prop­er­ties. Now note that as , , and for , we evi­dently must have

We can find such by inspect­ing the fol­low­ing illustration:

Evi­dently the req­ui­site assump­tions are sat­is­fied when is the small­est root of the equa­tion (but not for the larger root at !)

Remark. Note that the super­crit­i­cal case is essen­tial here. If then the equa­tion for has no solu­tions , and the argu­ment in the proof does not work. In fact, when , we have .

By an imme­di­ate adap­ta­tion of the proof of the pre­vi­ous lemma, we obtain

where is the small­est pos­i­tive solu­tion of . Let­ting , we see that

where is the small­est solu­tion of the equa­tion (which is pre­cisely the prob­a­bil­ity that the Pois­son ran­dom walk hits zero, by the iden­ti­cal proof to the lemma above). We have there­fore proved

Vari­ance of the giant com­po­nent size

To com­plete the proof of Part 2 of the giant com­po­nent the­o­rem, it remains to show that

To this end, let us consider

To esti­mate the terms in this sum, we con­di­tion on one of the components:

To pro­ceed, note that the event can be writ­ten as

In par­tic­u­lar, the event is inde­pen­dent of the edges for . There­fore, for , the con­di­tional law of given coin­cides with the (uncon­di­tional) law of , the con­ncted com­po­nent con­tain­ing in the induced sub­graph on the ver­tices :

As this quan­tity only depends on by the sym­me­try of the Erdös-Rényi model, we can evi­dently write

for , . In par­tic­u­lar, we obtain

Now note that, by its def­i­n­i­tion, is dis­trib­uted pre­cisely as the com­po­nent con­tain­ing ver­tex in the ran­dom graph model. We can there­fore show, repeat­ing exactly the proof of the mean size of the giant com­po­nent above, that

We have there­fore shown that

which evi­dently implies

This is what we set out to prove.

Remark. It should be noted that the proof of Part 2 did not depend on the value of , or even on the rate, in the def­i­n­i­tion of the set : any sequence that grows sub­lin­early to infin­ity would have given the same result. This sug­gests that all but a van­ish­ing frac­tion of ver­tices are con­tained in con­nected com­po­nents of order or . We find out only in the next lec­ture why the rate (for suf­fi­ciently large!) is impor­tant: only suf­fi­ciently large con­nected com­po­nents are guar­an­teed to inter­sect, while there might (and do) exist com­po­nents of order that are dis­joint from the giant com­po­nent. If we do not exclude the lat­ter, we will not be able to prove Part 1.

Many thanks to Weichen Wang for scrib­ing this lecture!

17. April 2013 by Ramon van Handel

## Lecture 4. Giant component (1)

Con­sider the Erdös-Rényi graph model . In pre­vi­ous lec­tures, we focused on the “high com­plex­ity regime”, i.e., as goes to infin­ity, is fixed. We dis­cussed top­ics such as clique num­bers and chro­matic num­bers. From now on, we shall con­sider the “low com­plex­ity regime”, where as goes to infin­ity, for a fixed con­stant . As before, let be the adja­cency matrix of . Then are i.i.d. Bernoulli ran­dom vari­ables with suc­cess prob­a­bil­ity .

The­o­rem 1 Let be the con­nected com­po­nent of that con­tains .

1. If , then in probability.
2. If , then in prob­a­bil­ity, for some .
3. If , then in distribution.

In the fol­low­ing lec­tures, we will aim to prove at least parts 1 and 2.

The explo­ration process

How to study ? We will explore by start­ing an “explo­ration process” at that moves around until all its sites have been vis­ited. This walk will be con­structed so that it hits each site once. So, the time it takes to explore all of is exactly . As a con­se­quence, study­ing reduces to study­ing a hit­ting time of a cer­tain ran­dom walk, and to the lat­ter we can apply mar­tin­gale theory.

At each time , we main­tain three sets of vertices:

Below is an illus­tra­tion of how these sets are updated on a sim­ple example.

• At , ini­tial­ize , and . Namely, only is active, all the ver­tices other than are unex­plored, and no ver­tices have been removed.

• At , update , and . Namely, all neigh­bors of are moved from the unex­plored set to the active set, and itself is removed.

• At , pick some and update , and . Namely, all unex­plored neigh­bors of are moved into the active set, and itself is removed.

• At time , we pick some ver­tex from the cur­rent active set , acti­vate all unex­plored neigh­bors of and remove itself.

This is a sort of local search along the con­nected com­po­nent : much like play­ing a game of Minesweeper! At each , the choice of can be made arbi­trar­ily (e.g., select­ing the ver­tex with the small­est index or ran­domly select­ing a ver­tex in ). The only require­ment is that it is nonan­tic­i­pat­ing (only depend­ing on the edges vis­ited up to time ). For exam­ple, we can­not pick the ver­tex in which has the largest num­ber of unex­plored neigh­bors, as this choice relies on unex­plored edges.

A for­mal descrip­tion of the “explo­ration process”:

• Ini­tial­ize , and .
• For , we set

where is a nonan­tic­i­pat­ing but oth­er­wise arbi­trary choice.

This process stops when there are no more active ver­tices. It hits each ver­tex in once and only once. At each time , we remove one ver­tex in . So the stop­ping time is exactly equal to the size of :

So, we only need to study the stop­ping time .

Recall that indi­cates whether there is an edge between ver­tices and , and . By construction,

Now, let’s do a thought exper­i­ment (wrong, but intu­itive). Let’s for­get for the moment that some sites were pre­vi­ously vis­ited, and assume that in each step all neigh­bors of are unvis­ited still (note that when is really large and is rel­a­tively small, this assump­tion makes sense). Then is the sum of inde­pen­dent ) vari­ables, which has a dis­tri­b­u­tion. This bino­mial vari­able is inde­pen­dent of the past because it only depends on unex­plored edges; in addi­tion, its dis­tri­b­u­tion does not depend on . There­fore, would be a ran­dom walk with incre­ment dis­tri­b­u­tion . Then, study­ing boils down to study­ing first time a Pois­son ran­dom walk hits zero! Of course, we can­not really ignore pre­vi­ously vis­ited sites, but this rough intu­ition nonethe­less cap­tures the right idea as and will serve as a guid­ing prin­ci­ple for the proof.

A com­par­i­son ran­dom walk

The rea­son that is not a ran­dom walk is that there are only edges (not ) to explore at time . We can arti­fi­cially cre­ate a ran­dom walk by adding “fic­ti­tious” points at each time as follows.

Let be i.i.d. for , , which are inde­pen­dent of . Define

(When , then and thus is unde­fined; in this case, we sim­ply add all vari­ables .)
Note that is the sum of edges from to . Since we have not explored yet, those edges are inde­pen­dent of all edges explored up to time (here we use that is nonan­tic­i­pat­ing). We there­fore see that is indeed a ran­dom walk with increment

More­over, since all are nonnegative,

as long as . It fol­lows that is dom­i­nated by the gen­uine ran­dom walk , that is,

We can now obtain bounds on by ana­lyz­ing hit­ting times of the ran­dom walk .

The sub­crit­i­cal case

Define the first time the com­par­i­son walk hits zero as

Since for , it is obvi­ous that

Now we study . The intu­ition is that as , is a ran­dom walk with neg­a­tive drift in the sub­crit­i­cal case . Thus , and in fact the hit­ting time has nice tails!

Lemma 2 Let and . Then for any pos­i­tive inte­ger ,

We will prove this lemma below. Using the lemma, we imme­di­ately obtain:

Corol­lary 3 If , then for any

Proof. Apply­ing the Lemma 2 and the union bound,

This corol­lary proves part 1 of The­o­rem 1. In fact, it turns out that the con­stant is tight: by using the sec­ond moment method, one can prove a match­ing lower bound on (see, for exam­ple, the lec­ture notes by van der Hof­s­tad), which implies that in fact in prob­a­bil­ity. The proof is not much more dif­fi­cult, but we pre­fer to move on to the super­crit­i­cal case.

Remark. It might seem some­what sur­pris­ing that the result we obtain is so sharp, con­sid­er­ing that we have blindly replaced by the larger quan­tity . How­ever, in going from to we do not lose as much as one might think at first sight. When is large and is rel­a­tively small, the excess term in the def­i­n­i­tion of is zero with high prob­a­bil­ity, as most ver­tices are unex­plored and the Bernoulli suc­cess prob­a­bil­ity of the is very small. With a bit of work, one can show that and will actu­ally stick together for times with prob­a­bil­ity going to one as . Thus, in the sub­crit­i­cal case where the ran­dom walk only lives for time steps, noth­ing is lost in going from to , and our rough intu­ition that should behave like a ran­dom walk as is vindicated.

To wrap up the sub­crit­i­cal case, it remains to prove the lemma.

Proof of Lemma 2. By the Markov inequality,

It remains to bound , which is a stan­dard exer­cise in mar­tin­gale theory.

Recall that

where are i.i.d. Define the moment gen­er­at­ing func­tion , and let

Since and is inde­pen­dent of ,

where we have used . So is a martingale.

In the case and ,

The inequal­ity is by Fatou’s lemma and the sec­ond equal­ity is by the optional stop­ping the­o­rem. To see the first equal­ity, note that if , then and as , while if , then for all and . Thus .

Next, we com­pute . Recall that . It has the same dis­tri­b­u­tion as the sum of i.i.d. vari­ables. For , we have . There­fore,

where the last inequal­ity is because for any . Now, by set­ting , we obtain that . Thus we have shown .

The super­crit­i­cal case

The goal of the fol­low­ing lec­tures is to prove part 2 of The­o­rem 1. More pre­cisely, we will prove:

The­o­rem 4 Let . Then

in prob­a­bil­ity, where is the small­est pos­i­tive solu­tion of the equa­tion . More­over, there is such that all but one of the com­po­nents have size , with prob­a­bil­ity tend­ing to as .

This the­o­rem says that with prob­a­bil­ity tend­ing to , there is a unique giant com­po­nent whose size is , and all other com­po­nents are small with size .

Here we pro­vide some vague intu­ition for this the­o­rem. When , the ran­dom walk sat­is­fies , i.e., has pos­i­tive drift. Then ! In fact, the fur­ther away it starts from , the smaller the prob­a­bil­ity it will ever hit . Con­sider the two situations:

• dies quickly: this implies that the com­po­nent is small.
• lives long: then it must live very long, as once it gets far away from , the prob­a­bil­ity of return­ing is very small. This implies that the com­po­nent must be very large (if we pre­tend that ).

Of course, is not (obvi­ously even­tu­ally hits ). But the intu­ition explains that there can­not be com­po­nents of inter­me­di­ate size: given any ver­tex , either is small (), or it must get very large (, say). In fact, we will find that all com­po­nents of size must grow all the way to . How­ever, any pair of large com­po­nents must inter­sect with high prob­a­bil­ity, as there are many poten­tial edges between them! There­fore, all ver­tices with should be in the same giant com­po­nent. We then show that the num­ber of such ver­tices is with high probability.

Many thanks to Tracy Ke for scrib­ing this lecture!

06. April 2013 by Ramon van Handel

## Next lecture: April 4

Just a reminder that next week (March 21) is Spring Break, while the week after (March 28) there will be no lec­ture due to the ORFE/PACM col­lo­quium of Elchanan Mos­sel.

The next Sto­chas­tic Analy­sis Sem­i­nar lec­ture will be on April 4. We will start fresh with a new topic: the study of the giant com­po­nent of an Erdös-Rényi graph.

15. March 2013 by Ramon van Handel

## Lecture 3. Chromatic number

Let ${C}$ be set of inte­gers that rep­re­sent col­ors. A ver­tex col­or­ing of a graph ${G=([n], E)}$ is an assign­ment ${c\,:\,\{1, \ldots, n\} \rightarrow C}$ of a color ${c(i) \in C}$ to each ver­tex ${i \in [n]}$. Fur­ther­more a ver­tex col­or­ing ${c}$ is said to be proper if ${c(i)\neq c(j)}$ for all ${(i,j) \in E}$. The chro­matic num­ber ${\chi(G)}$ of a graph ${G}$ is the small­est num­ber ${|C|}$ of col­ors needed for a proper ver­tex col­or­ing to exist. In this lec­ture, any col­or­ing is a proper ver­tex col­or­ing. All logs are in base ${2}$.

The­o­rem [Bol­lobas, 1988]
The chro­matic num­ber ${\chi(G)}$ of a ran­dom graph ${G\sim G(n,\frac12)}$ satisfies

$\displaystyle \chi(G) =\frac{n}{2\log n}(1+o_P(1))$

1. Basic properties

In this sec­tion, we begin by review­ing some basic prop­er­ties of the chro­matic num­ber, and in par­tic­u­lar how it relates to inde­pen­dent sets. Recall that an inde­pen­dent set ${S \subset [n]}$ of a graph ${G=([n], E)}$ is a set of ver­tices such that ${i,j \in S \Rightarrow (i,j) \notin E}$. Inde­pen­dent sets are some­times called sta­ble sets. Denote by ${\bar G=([n], \bar E)}$ the com­ple­ment graph of ${G}$ where ${(i,j) \in \bar E}$ iff ${(i,j) \notin E}$. If ${S}$ is an inde­pen­dent set of ${G}$, then it is a clique in ${\bar G}$. The largest inde­pen­dent set in ${G}$ is called inde­pen­dence num­ber of ${G}$ and denoted by ${\alpha(G)}$.

Propo­si­tion For any graph ${G=([n],E)}$ with inde­pen­dence num­ber ${\alpha(G)}$, clique num­ber ${\omega(G)}$ and chro­matic num­ber ${\chi(G)}$ the fol­low­ing holds

1. ${1\le \chi(G) \le n}$
2. ${\chi(G) \ge \omega(G)}$
3. ${n \le \chi(G)\alpha(G)}$

Proof: Trivial. $\Box$

2. Chro­matic, clique and inde­pen­dence numbers

Our goal is to study the chro­matic num­ber of a ran­dom graph ${G \sim G(n,\frac12)}$. It actu­ally builds upon the clique num­ber that we stud­ied dur­ing last lec­ture. Indeed, we will use the fol­low­ing obser­va­tion: if ${G \sim G(n,\frac12)}$ then so does the com­ple­ment graph ${\bar G}$ of ${G}$. It implies that the inde­pen­dence num­ber ${\alpha(G)}$ has the same dis­tri­b­u­tion as the clique num­ber ${\omega(G)}$. We know from last lec­ture that ${\omega(G)=(2\log n)(1+o(1))}$. There­fore, it fol­lows from the above propo­si­tion that

$\displaystyle \chi(G) \ge \frac{n}{\alpha(G)}= \frac{n}{2\log n}(1+o(1))\,.$

Our main the­o­rem sug­gests that this sim­ple bound is, in fact, tight. Prov­ing this requires a stronger lower bound on clique of a ran­dom graph.

Define ${m=\lfloor n/\ln^2 n\rfloor}$ and let ${V \subset [n]}$ be a sub­set of ${|V|=m}$ ver­tices and observe that induced sub­graph ${G_V=(V, E \cap [m]^2)}$ restricted to ver­tices in ${V}$ has dis­tri­b­u­tion ${G(m,\frac12)}$.

Define

$\displaystyle \bar \alpha_m=\min_{\substack{V\subset [n]\\ |V|=m}} \alpha(G_{V})$

That is: every ${m}$ ver­tex sub­graph con­tains an inde­pen­dent set of size ${\bar \alpha_m}$.

Con­sider now the fol­low­ing col­or­ing pro­ce­dure to pro­duce a proper col­or­ing. Pull out inde­pen­dent sets of size ${\bar \alpha_m}$ one by one and give each a dis­tinct color. Accord­ing to the def­i­n­i­tion of ${\bar \alpha_m}$, as long as there are at least ${m}$ ver­tices, this is pos­si­ble. If there are less than ${m}$ ver­tices left, give each a dis­tinct color.

The above algo­rithm gives one pos­si­ble way of col­or­ing graph ${G}$ and thus the out­put num­ber is an upper bound on the chro­matic num­ber ${\chi(G)}$. Let us now com­pute this upper bound. By def­i­n­i­tion of ${\bar \alpha_m}$, we have

$\displaystyle \chi(G)\le \Big\lceil \frac{n-m}{\bar \alpha_m}\Big\rceil + m \le \frac{n}{\bar \alpha_m} +m\,. \ \ \ \ \ (1)$

There­fore, to find an upper bound on ${\chi(G)}$, we need to find a lower bound on ${\bar \alpha_m}$ for an appro­pri­ately cho­sen ${m}$. To that end, observe that

$\displaystyle \begin{array}{rcl} \mathbb{P}(\bar \alpha_m

There­fore, we need to prove a bound on ${\mathbb{P}(\omega(G_{V}), uni­formly in ${V}$. This can be done using con­cen­tra­tion prop­er­ties of a suit­able martingale.

3. Azuma-Hoeffding inequality

Mar­tin­gales have use­ful con­cen­tra­tion prop­er­ties. Specif­i­cally the fol­low­ing lemma holds.

Lemma [Azuma-Hoeffding inequal­ity.]
Let ${(\Omega, \mathcal{F}, \{\mathcal{F}_i\}_{i \ge 0}, \mathbb{P})}$ be a fil­tered space and let ${X}$ be a ran­dom vari­able on ${(\Omega, \mathcal{F}, \mathbb{P})}$. Assume that the mar­tin­gale ${X_i=\mathbb{E}[X|\mathcal{F}_i], i\ge 0}$ is such that for all ${i \ge 1}$,

$\displaystyle |X_{i}-X_{i-1}|\le 1\,, \qquad \text{a.s.}$

Then for any pos­i­tive inte­ger ${N}$ and any ${t>0}$, it holds,

$\displaystyle \mathbb{P}(X_N-X_0\ge t) \le \exp\Big(-\frac{t^2}{2N}\Big)$

and

$\displaystyle \mathbb{P}(X_N-X_0\le -t) \le \exp\Big(-\frac{t^2}{2N}\Big)$

Proof: We assume the fol­low­ing inequal­ity due to Hoeffd­ing. For any ran­dom vari­able ${Z}$ such that ${|Z| \le 1}$ a.s. and any ${s>0}$, it holds

$\displaystyle \mathbb{E}[e^{sZ}]\le e^{\frac{s^2}{2}}\,.$

Now, using a Cher­noff bound, we get for any ${s>0}$,

$\displaystyle \begin{array}{rcl} \mathbb{P}(X_N-X_0>t)&=&\mathbb{P}\Big(\sum_{i=1}^N\{X_i-X_{i-1}\}>t\Big)\\ &\le& e^{-st}\mathbb{E}\exp\Big(s\sum_{i=1}^N\{X_i-X_{i-1}\}\Big)\\ &=&e^{-st}\mathbb{E}\prod_{i=1}^N\exp\Big(s\{X_i-X_{i-1}\}\Big)\\ &=&e^{-st}\mathbb{E}\prod_{i=1}^N\mathbb{E}\Big[\exp\Big(s\{X_i-X_{i-1}\}\Big)\Big|\mathcal{F}_{i-1}\Big]\\ \end{array}$

where ${\mathcal{F}_{i}=\sigma(X_1, \ldots, X_i)}$. The above two dis­plays yield that

$\displaystyle \mathbb{P}(X_N-X_0>t)\le \exp\Big(\inf_{s>0}\Big\{\frac{Ns^2}{2} -st\Big\}\Big)=\exp\Big(-\frac{t^2}{2N}\Big)\,.$

The sec­ond part of the proof fol­lows by apply­ing the same argu­ment to the mar­tin­gale ${(-X_i)_{i\ge 0}}$. $\Box$

Con­sider the lex­i­co­graphic order­ing of ${[n]^2}$ and let ${E_1, \ldots, E_N \in \{0,1\}}$ be ${N={n \choose 2}}$ iid Bernoulli ran­dom vari­ables with para­me­ter ${1/2}$ indi­cat­ing the pres­ence of an edge in a graph ${G\sim G(n,\frac12)}$. Define the ${\sigma}$–alge­bra ${\mathcal{F}_i=\sigma(E_1, \ldots E_i), i=1, \ldots, N}$. We are going to apply the Azuma-Hoeffding inequal­ity to the (Doob) mar­tin­gale ${Y_i=\mathbb{E}[Y|\mathcal{F}_i]\,, \quad i=1, \ldots, N}$ where ${Y}$ is max­i­mal num­ber of edge-disjoint ${k}$–cliques in ${G}$.

Note first that ${|Y_i-Y_{i-1}|\le 1}$ a.s., since adding/removing one edge can add/remove at most one edge dis­joint ${k}$–clique. More­over, this inequal­ity would not hold if we had cho­sen ${Y}$ to be the num­ber cliques of size ${k}$ (not nec­es­sar­ily dis­joint). Indeed, adding or remov­ing an edge can cre­ate or destroy many over­lap­ping cliques.

It fol­lows that,

$\displaystyle \begin{array}{rcl} \mathbb{P}[\omega(G)

There­fore, apply­ing the Azuma-Hoeffding inequal­ity, we get

$\displaystyle \mathbb{P}[\omega(G)

It remains to show that ${\mathbb{E}[Y]}$ is suf­fi­ciently large. Note first that ${Y \ge X}$, where is ${Y}$ is the num­ber of ${k}$–cliques that do not share an edge with any other ${k}$–clique of the graph.

4. A strong lower bound on the clique number

Fix pos­i­tive inte­gers ${m}$ and

$\displaystyle k=(2-\varepsilon+o(1))\log m$

and let ${X}$ denote the num­ber of ${k}$ cliques in ${G \sim G(m,\frac12)}$ that do not share an edge with any other ${k}$–clique of the graph. Then

$\displaystyle \mathbb{E}[X]\ge m^{(2-\varepsilon)a+o(1)}$

for all ${a\in (0,1)}$. Here the asymp­totic nota­tion nota­tions ${o(1)}$ are as ${m \rightarrow \infty}$.

Proof: Define ${M=\left\lceil 2^ak2^{\frac{k-1}{2}}\right\rceil\ge 4k}$ (for ${m}$ large enough) for some ${a \in (1,2)}$ to be cho­sen later.

More­over, note that for ${m}$ large enough,

$\displaystyle M\le 8m^{1-\frac{\varepsilon}2 +o(1)}\le m$

so that ${X \ge X'}$ where ${X'}$ is the num­ber of ${k}$ cliques in ${G \sim G(M,\frac12)}$ that do not share an edge with any other ${k}$–clique of the graph ${G}$. Let ${G \sim G(M, \frac12)}$.

For any ${S \in [M]}$ define the indicator:

$\displaystyle I_S=1\{S \text{ is a clique of size} \ k \ \text{in} \ G\}.$

More­over for any set ${S}$, let ${Z(S)}$ denote the num­ber of ${k}$–cliques in ${G}$, other than ${S}$ itself, that share at least two ver­tices with ${S}$. Observe that

$\displaystyle \begin{array}{rcl} \mathbb{E}[X']&=&\mathbb{E}\sum_{\substack{S \subset [M] \\ |S| =k}}I_S1\{Z(S)=0\}\\ &=&{M\choose k}\mathbb{P}(I=1, Z=0)\qquad \text{where } I=I_{[k]}\,, \ Z=Z([k])\\ &=&{M \choose k}\Big(\frac12\Big)^{k \choose 2}\mathbb{P}(Z=0|I=1)\,, \end{array}$

We bound ${\mathbb{P}(Z=0|I=1)}$ as follows

$\displaystyle \begin{array}{rcl} \mathbb{P}(Z=0|I=1)&=&1-\mathbb{P}(Z\ge 1|I=1)\\ &\ge& 1-\mathbb{E}(Z|I=1)\\ &=&1-\sum_{\substack{S \subset [M], |S|=k\\ |S\cap [k]| \ge 2}}\mathbb{P}(I_S=1)\\ &=&1-\sum_{s=2}^{k-1}\underbrace{{k\choose s}{M-k \choose k-s}\Big(\frac12\Big)^{{k\choose 2}-{s\choose 2}}}_{F_s}\\ \end{array}$

The fol­low­ing bound holds for all ${2\le s \le k/2}$,

$\displaystyle \begin{array}{rcl} \frac{F_s}{F_2}&=&\frac{(M-2k+2)!}{(M-2k+s)!}\Big[ \frac{(k-2)!}{(k-s)!} \Big]^2\frac2{s!}2^{\frac{(s+1)(s-2)}{2}}\\ &\le& \frac2{s!}\Big(\frac{(k-2)^22^{\frac{s+1}2}}{M-2k+2} \Big)^{s-2}\\ &\le&\frac1{(s-2)!}\Big(\frac{2k^22^{\frac{k/2+1}{2}}}{M} \Big)^{s-2}\qquad \text{for} \ M\ge 4k\\ &\le&\frac1{(s-2)!}(2^{2+a}k2^{-\frac{k}4})^{s-2} \end{array}$

It yields

$\displaystyle \begin{array}{rcl} \sum_{2\le s \le k/2}\frac{F_s}{F_2}&\le & \exp\Big(2^{2+a}k2^{-\frac{k}4}\Big)=1+o(1)\\ \end{array}$

More­over, for ${s> k/2}$, ${M \ge k}$, it holds

$\displaystyle \begin{array}{rcl} {M-k \choose k-s}&\le& {M-k \choose s}\frac{s!(M-k-s)!}{(k-s)!(M-2k+s)!}\\ &\le& {M-k \choose s}\Big(\frac{s}{M-k+s}\Big)^k\\ &\le & {M-k \choose s}\Big(\frac{k}{M-k/2}\Big)^{k}\\ \end{array}$

Hence,

$\displaystyle \begin{array}{rcl} F_s&=& {k\choose k-s}{M-k \choose k-s}\Big(\frac12\Big)^{{k\choose 2}-{s\choose 2}}\\ &\le& F_{k-s}\Big(\frac{k}{M-k/2}\Big)^{k}\Big(\frac12\Big)^{{k-s\choose 2}-{s\choose 2}}\\ &\le & F_{k-s}\Big(\frac{k2^{\frac{k-1}2}}{M-k/2}\Big)^{k}\\ &\le & F_{k-s}\Big(\frac{2^{-a}M}{M-k/2}\Big)^{k}\\ &\le &F_{k-s}o(1)\,. \end{array}$

There­fore,

$\displaystyle \sum_{k/2\le s \le k-1}\frac{F_s}{F_2}\le \sum_{2\le s \le k/2}\frac{F_s}{F_2}o(1)=o(1)\\$

Thus,

$\displaystyle \mathbb{P}(Z=0|I=1)\ge 1-F_2(1+o(1))\,.$

More­over,

$\displaystyle \begin{array}{rcl} F_2&=&2{k \choose 2}{M-k \choose k-2} \frac{1}{2^{k \choose 2}}\\ &=& k^2\Big(\frac{M-k}{k-2}\Big)^{k-2}2^{-\frac{k(k-1)}{2}}(1+o(1))\\ &=& \frac{k^2}{M^2}\Big(\frac{M}{k2^{\frac{k-1}{2}}}\Big)^{k}(1+o(1))\\ &=& \frac{k^22^{ak}}{M^2}(1+o(1))\\ &\le&\frac{2}{2^{2a}}\Big(\frac{2^a}{2}\Big)^k(1+o(1))=o(1)\,, \end{array}$

since ${2^a<2}$.

To con­clude the proof, observe that by Stir­ling, since ${k=o(n)}$,

$\displaystyle \begin{array}{rcl} {M \choose k}\Big(\frac12\Big)^{k \choose 2}&\ge&\Big(\frac{M}{k2^{\frac{k-1}{2}}}\Big)^k(1+o(1))\\ &=&2^{ak}(1+o(1))=m^{(2-\varepsilon) a+o(1)}\,. \end{array}$

$\Box$

Let ${G \sim G(m, \frac12)}$ and observe that

$\displaystyle (2-\varepsilon+o(1))\log m=(2-\varepsilon+o(1))\log n$

We can there­fore apply the pre­vi­ous propo­si­tion together with~(2), to get

$\displaystyle \mathbb{P}[\omega(G)<(2-\varepsilon+o(1))\log n]\le \exp\Big(-\frac{m^{2(2-\varepsilon)a+o(1)}}{n(n-1)}\Big)$

5. Proof of the main theorem

Since

$\displaystyle {n \choose m}\le 2^n=2^{m^{1+o(1)}}\,,$

we get for ${k=(2-\varepsilon+o(1))\log n}$,

$\displaystyle \begin{array}{rcl} \mathbb{P}(\bar \alpha_m

Thus ${\bar \alpha_m \ge (2\log n)(1+o_P(1))}$. Together with~(1), it yields

$\displaystyle \begin{array}{rcl} \chi(G)&\le&\frac{n}{k}(1+o_P(1))+m \\ &=&\frac{n}{2\log n}(1+o_P(1))+o\Big(\frac{n}{\log n}\Big)\\ &=&\frac{n}{2\log n}(1+o_P(1)) \end{array}$

Which com­pletes the proof of our theorem.

Lec­ture and scrib­ing by Philippe Rigol­let

14. March 2013 by Philippe

## Lecture 2. Clique number

In this lec­ture all logs are in base ${2}$. We will prove the following.

The­o­rem For the cen­tered and nor­mal­ized clique number

$\displaystyle \frac{\omega\left(G(n, \frac12)\right) - 2 \log n}{\log \log n}\xrightarrow{n\to\infty}-2 \quad\text{in probability.}$

That is, as $n\to\infty$, the clique num­ber of the Erdös-Rényi graph $G(n,\frac12)$ is $\omega\left(G(n, \frac12)\right)=2\log n-(2+o(1))\log\log n$.

Proof: The proof is divided into two parts. First, we show that the clique num­ber can­not be too big using a union bound. Then we show that the clique num­ber can­not be too small using the sec­ond moment method. In the fol­low­ing, $G_n$ denotes an Erdös-Rényi graph $G(n,\frac12)$.

For the first part one has

$\displaystyle \begin{array}{rcl} {\mathbb P}(\omega(G_n) \geq k) & = & {\mathbb P}( \exists S \subset [n], \; \text{s.t.} \; |S|=k \; \text{and} \; S \; \text{is a clique in} \; G_n) \\ & \leq & \sum_{S \subset [n], |S|=k} {\mathbb P}(S \; \text{is a clique in} \; G_n) \notag \\ & = & {n \choose k} \left(\frac12\right)^{{k \choose 2}} \\ & \leq & \left(\frac{e n}{k} \right)^k 2^{- \frac{k(k-1)}{2}} \\ & = & 2^{k \left( \log n - \log k + \log e- \frac{k-1}{2}\right)}. \end{array}$

Thus, choos­ing $k=2\log n - (2 - \epsilon) \log \log n$, we obtain

${\mathbb P}(\omega(G_n) \geq 2\log n - (2 - \epsilon) \log \log n) \le n^{ - \frac{\epsilon}{2} \log \log n + \frac{1}{2} + \log e} \xrightarrow{n \rightarrow \infty} 0$

for every ${\epsilon >0}$, where we used that $k\ge\log n$ for large $n$.

For the sec­ond part it is use­ful to intro­duce some nota­tion. Define

$\displaystyle {X_S = 1\{S \; \text{is a clique in} \; G_n\}},\qquad {Y_k = \sum_{S \subset [n], |S|=k} X_S}$.

In par­tic­u­lar, ${\omega(G_n) < k}$ iff ${Y_k=0}$. Thus we want to show that for ${k=2\log n - (2 + \epsilon) \log \log n}$ one has ${{\mathbb P}(Y_k = 0) \to 0}$. Using the triv­ial obser­va­tion that $x=0$ implies $(x-y)^2=y^2$, we get

$\displaystyle {\mathbb P}(Y_k=0) \leq {\mathbb P}((Y_k - {\mathbb E} Y_k)^2 = ({\mathbb E} Y_k)^2) \leq \frac{\text{Var}(Y_k)}{({\mathbb E} Y_k)^2}$

where we have used Markov’s inequal­ity. Note that by lin­ear­ity of the expec­ta­tion, ${\mathbb E} Y_k = {n \choose k} \left(\frac12\right)^{k\choose 2}$. Fur­ther­more, we can write

$\displaystyle \text{Var}(Y_k) = \sum_{S \subset [n], |S|=k} \text{Var}(X_S) + \sum_{S, T \subset [n], |S|=|T|=k, S \neq T} \{ {\mathbb E} X_S X_T - ({\mathbb E} X_S) ({\mathbb E} X_T) \}.$

As ${X_S}$ are boolean ran­dom vari­ables we have ${\text{Var}(X_S) \leq {\mathbb E} X_S}$ and thus

$\displaystyle \frac{\sum_{S \subset [n], |S|=k} \text{Var}(X_S)}{\left( {\mathbb E} Y_k \right)^2} \leq \frac{\sum_{S \subset [n], |S|=k} {\mathbb E} X_S}{\left( {\mathbb E} Y_k \right)^2} = \frac{1}{{n \choose k} \left(\frac12\right)^{k\choose 2}},$

which tends to ${0}$ for ${k=2\log n - (2 + \epsilon) \log \log n}$ (see the first part of the proof and use the inequal­ity ${{n \choose k} \geq \left(\frac{n}{k}\right)^k}$). Thus it remains to show that the fol­low­ing quan­tity tends to ${0}$:

$\displaystyle \frac{\sum_{S, T \subset [n], |S|=|T|=k, S \neq T} \{{\mathbb E} X_S X_T - ({\mathbb E} X_S) ({\mathbb E} X_T)\}}{\left({\mathbb E} Y_k\right)^2} .$

First note that, by the inde­pen­dence of the edges, for ${S, T}$ with ${|S \cap T| \leq 1}$ we have that ${X_S}$ and ${X_T}$ are inde­pen­dent, so that in the numer­a­tor of the above quan­tity one can restrict to ${S, T}$ with ${|S \cap T| \geq 2}$. Now by an ele­men­tary rea­son­ing we have (with ${S_0}$ being an arbi­trary sub­set of ${k}$ vertices)

$\displaystyle \begin{array}{rcl} && \sum_{S, T \subset [n], |S|=|T|=k, S \neq T, |S \cap T| \geq 2} {\mathbb E} X_S X_T \\ && = \sum_{S, T \subset [n], |S|=|T|=k, S \neq T, |S \cap T| \geq 2} {\mathbb P}(X_S = 1 \; \text{and} \; X_T = 1) \\ && = \sum_{S, T \subset [n], |S|=|T|=k, S \neq T, |S \cap T| \geq 2} {\mathbb P}(X_S = 1) {\mathbb P}(X_T =1 | X_S = 1) \\ && = \left( \sum_{T \subset [n], |T|=k, T \neq S_0, |S_0 \cap T| \geq 2} {\mathbb P}(X_T = 1 | X_{S_0} = 1) \right) \left(\sum_{S \subset [n], |S|=k} {\mathbb P}(X_S=1) \right) \\ && = \left( \sum_{T \subset [n], |T|=k, T \neq S_0, |S_0 \cap T| \geq 2} {\mathbb P}(X_T = 1 | X_{S_0} = 1) \right) \left({n \choose k} {\mathbb E} X_S \right) . \end{array}$

Thus we are now left with prov­ing that the fol­low­ing quan­tity goes to ${0}$:

$\displaystyle \frac{\sum_{T \subset [n], |T|=k, T \neq S_0, |S_0 \cap T| \geq 2} {\mathbb P}(X_T = 1 | X_{S_0} = 1)}{{n \choose k} \left(\frac12 \right)^{- {k \choose 2}}} . \ \ \ \ \ (1)$

Clearly one has

$\displaystyle {\mathbb P}(X_T = 1 | X_{S_0} = 1) = \left( \frac12 \right)^{{k \choose 2} - {|T \cap S_0| \choose 2}} ,$

which shows that (1) can be rewrit­ten as

$\displaystyle \sum_{s=2}^{k-1} \frac{{k \choose s} {n-k \choose k-s}}{{n \choose k}} 2^{{s \choose 2}} . \ \ \ \ \ (2)$

Now note that since

$\displaystyle {n-1 \choose k-1} = \frac{k}{n} {n \choose k} ,$

one has

$\displaystyle {n-k \choose k-s} \leq {n-s \choose k-s} = \left( \prod_{\alpha=1}^s \frac{k-\alpha}{n-\alpha} \right) {n \choose k} \leq \left(\frac{k}{n}\right)^s {n \choose k} .$

Using ${ {k \choose s} \leq \left(\frac{e k}{s}\right)^s}$ one obtains that (2) is bounded from above by

$\displaystyle \sum_{s=2}^{k-1} \left(\frac{k}{s}\right)^s \left(\frac{k}{n}\right)^s 2^{{s \choose 2}} = \sum_{s=2}^{k-1} 2^{s \left(2 \log k - \log n + \frac{s}{2} - \log s + \log e - \frac12\right)} .$

As $\frac{s}{2}-\log s$ is a con­vex func­tion and as ${2 \leq s \leq k}$, one has ${\frac{s}{2} - \log s \leq \max(0, \frac{k}{2} - \log k)}$. Thus for ${k}$ large enough the expo­nent in the above dis­play is bounded from above by ${\log k - \log n + \frac{k}{2} + c}$, and for ${k=2\log n - (2 + \epsilon) \log \log n}$ this lat­ter is bounded by ${- \frac{\epsilon}{2} \log \log n + c}$. Thus we proved that (2) is bounded from above by

$\displaystyle \sum_{s=2}^{k-1} 2^{ - s (\frac{\epsilon}{2} \log \log n - c) } ,$

which tends to ${0}$ as ${n}$ tends to infin­ity, con­clud­ing the proof. $\Box$

07. March 2013 by Sebastien Bubeck