## Lecture 5. Giant component (2)

Consider the Erdös-Rényi graph model , and denote as usual by the connected component of the graph that contains the vertex . In the last lecture, we focused mostly on the subcritical case , where we showed that . Today we will begin developing the supercritical case , where for a suitable constant . In particular, our aim for this and next lecture is to prove the following theorem.

Theorem. Let . Then

where is the smallest positive solution of the equation . Moreover, there is a such that all but one of the components have size with probability tending to as .

Beginning of the proof. Define the set

The proof of the Theorem consists of two main parts:

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

Part 1 states that all “large” components of the graph must intersect, forming one giant component. Some intuition for why this is the case was given at the end of the previous lecture. Part 2 computes the size of this giant component. In this lecture, we will concentrate on proving Part 2, and we will find out where the mysterious constant comes from. In the next lecture, we will prove Part 1, and we will develop a detailed understanding of why all large components must intersect.

Before we proceed, let us complete the proof of the Theorem assuming Parts 1 and 2 have been proved. First, note that with probability tending to one, the set is itself a connected component. Indeed, if and then must lie in disjoint connected components by the definition of . On the other hand, with probability tending to one, all must lie in the same connected component by Part 1. Therefore, with probability tending to one, the set forms a single connected component of the graph. By Part 2, the size of this component is , while by the definition of , all other components have size . This completes the proof.

The remainder of this lecture is devoted to proving Part 2 above. We will first prove that the claim holds on average, and then prove concentration around the average. More precisely, we will show:

1. .
2. .

Together, these two claims evidently prove Part 2.

Mean size of the giant component

We begin by writing out the mean size of the giant component:

where we note that does not depend on the vertex by the symmetry of the Erdös-Rényi model. Therefore, to prove convergence of the mean size of the giant component, it suffices to prove that

This is what we will now set out to accomplish.

In the previous lecture we defined exploration process . We showed that

and that for

where is an arbitrary nonanticipating choice, say, (recall that denotes the adjacency matrix of the random graph). As are i.i.d. and as edges emanating from the set of unexplored vertices have not yet appeared in previous steps, the process is “almost'' a random walk: it fails to be a random walk as we only add Bernoulli variables in each iteration, rather than a constant number. In the last lecture, we noted that we can estimate from above by a genuine random walk by adding some fictitious vertices. To be precise, we define

where are i.i.d. independent of the (if , then and thus is undefined; in this case, we simply add all variables ). In the present lecture, we also need to bound from below. To this end, we introduce another process as follows:

where is the set consisting of the first elements of in increasing order of the vertices (if , we add variables ). The idea behind these processes is that is engineered, by including “fictitious'' vertices, to always add i.i.d. Bernoulli variables in every iteration, while is engineered, by including “fictitious'' vertices when is small and omitting vertices when is large, to always add i.i.d. Bernoulli variables in every iteration. The following facts are immediate:

• is a random walk with i.i.d. increments.
• is a random walk with i.i.d. increments.
• for all .
• for all on the event .

To see the last property, note that the exploration process can only explore as many vertices as are present in the connected component , so that for all ; therefore, in this situation only the second possibility in the definition of occurs, and it is obvious by construction that then (nonetheless, the first possibility in the definition must be included to ensure that is a random walk).

We now define the hitting times

Then we evidently have

(Note how we cleverly chose the random walk precisely so that whenever ). We have therefore reduced the problem of computing to computing the hitting probabilities of random walks. Now we are in business, as this is something we know how to do using martingales!

The hitting time computation

Let us take a moment to gather some intuition. The random walks and have increments distributed as and , respectively. As , both increment distributions converge to a distribution, so we expect that where is the first hitting time of the Poisson random walk. On the other hand, as , we expect that . The problem then reduces to computing the probability that a Poisson random walk ever hits the origin. This computation can be done explicitly, and this is precisely where the mysterious constant comes from!

We now proceed to make this intuition precise. First, we show that the probability can indeed be replaced by , as one might expect.

Lemma. as .

Proof. We need to show that

Note that as when ,

We can evidently write

where and

Choosing , we obtain for . Therefore,

This completes the proof.

By the above Lemma, and a trivial upper bound, we obtain

To complete computation of the mean size of the giant component, it therefore remains to show that and converge to . In fact, we can compute these quantities exactly.

Lemma. Let . Then

where is the smallest positive solution of .

Proof. Recall the martingale used in last lecture:

Suppose that and . Then

The first equality holds since if then and , while if then and . The second equality holds by dominated convergence since , and the third equality is by the optional stopping theorem.

Now suppose we can find such that as . Then we have

by dominated convergence. Thus, evidently, it suffices to find with the requisite properties. Now note that as , , and for , we evidently must have

We can find such by inspecting the following illustration:

Evidently the requisite assumptions are satisfied when is the smallest root of the equation (but not for the larger root at !)

Remark. Note that the supercritical case is essential here. If then the equation for has no solutions , and the argument in the proof does not work. In fact, when , we have .

By an immediate adaptation of the proof of the previous lemma, we obtain

where is the smallest positive solution of . Letting , we see that

where is the smallest solution of the equation (which is precisely the probability that the Poisson random walk hits zero, by the identical proof to the lemma above). We have therefore proved

Variance of the giant component size

To complete the proof of Part 2 of the giant component theorem, it remains to show that

To this end, let us consider

To estimate the terms in this sum, we condition on one of the components:

To proceed, note that the event can be written as

In particular, the event is independent of the edges for . Therefore, for , the conditional law of given coincides with the (unconditional) law of , the conncted component containing in the induced subgraph on the vertices :

As this quantity only depends on by the symmetry of the Erdös-Rényi model, we can evidently write

for , . In particular, we obtain

Now note that, by its definition, is distributed precisely as the component containing vertex in the random graph model. We can therefore show, repeating exactly the proof of the mean size of the giant component above, that

We have therefore shown that

which evidently 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 definition of the set : any sequence that grows sublinearly to infinity would have given the same result. This suggests that all but a vanishing fraction of vertices are contained in connected components of order or . We find out only in the next lecture why the rate (for sufficiently large!) is important: only sufficiently large connected components are guaranteed to intersect, while there might (and do) exist components of order that are disjoint from the giant component. If we do not exclude the latter, we will not be able to prove Part 1.

Many thanks to Weichen Wang for scribing this lecture!

17. April 2013 by Ramon van Handel
Categories: Random graphs | Comments Off

## Lecture 4. Giant component (1)

Consider the Erdös-Rényi graph model . In previous lectures, we focused on the “high complexity regime”, i.e., as goes to infinity, is fixed. We discussed topics such as clique numbers and chromatic numbers. From now on, we shall consider the “low complexity regime”, where as goes to infinity, for a fixed constant . As before, let be the adjacency matrix of . Then are i.i.d. Bernoulli random variables with success probability .

Theorem 1 Let be the connected component of that contains .

1. If , then in probability.
2. If , then in probability, for some .
3. If , then in distribution.

In the following lectures, we will aim to prove at least parts 1 and 2.

The exploration process

How to study ? We will explore by starting an “exploration process'' at that moves around until all its sites have been visited. This walk will be constructed so that it hits each site once. So, the time it takes to explore all of is exactly . As a consequence, studying reduces to studying a hitting time of a certain random walk, and to the latter we can apply martingale theory.

At each time , we maintain three sets of vertices:

Below is an illustration of how these sets are updated on a simple example.

• At , initialize , and . Namely, only is active, all the vertices other than are unexplored, and no vertices have been removed.

• At , update , and . Namely, all neighbors of are moved from the unexplored set to the active set, and itself is removed.

• At , pick some and update , and . Namely, all unexplored neighbors of are moved into the active set, and itself is removed.

• At time , we pick some vertex from the current active set , activate all unexplored neighbors of and remove itself.

This is a sort of local search along the connected component : much like playing a game of Minesweeper! At each , the choice of can be made arbitrarily (e.g., selecting the vertex with the smallest index or randomly selecting a vertex in ). The only requirement is that it is nonanticipating (only depending on the edges visited up to time ). For example, we cannot pick the vertex in which has the largest number of unexplored neighbors, as this choice relies on unexplored edges.

A formal description of the “exploration process'':

• Initialize , and .
• For , we set

where is a nonanticipating but otherwise arbitrary choice.

This process stops when there are no more active vertices. It hits each vertex in once and only once. At each time , we remove one vertex in . So the stopping time is exactly equal to the size of :

So, we only need to study the stopping time .

Recall that indicates whether there is an edge between vertices and , and . By construction,

Now, let's do a thought experiment (wrong, but intuitive). Let's forget for the moment that some sites were previously visited, and assume that in each step all neighbors of are unvisited still (note that when is really large and is relatively small, this assumption makes sense). Then is the sum of independent ) variables, which has a distribution. This binomial variable is independent of the past because it only depends on unexplored edges; in addition, its distribution does not depend on . Therefore, would be a random walk with increment distribution . Then, studying boils down to studying first time a Poisson random walk hits zero! Of course, we cannot really ignore previously visited sites, but this rough intuition nonetheless captures the right idea as and will serve as a guiding principle for the proof.

A comparison random walk

The reason that is not a random walk is that there are only edges (not ) to explore at time . We can artificially create a random walk by adding “fictitious'' points at each time as follows.

Let be i.i.d. for , , which are independent of . Define

(When , then and thus is undefined; in this case, we simply add all variables .)
Note that is the sum of edges from to . Since we have not explored yet, those edges are independent of all edges explored up to time (here we use that is nonanticipating). We therefore see that is indeed a random walk with increment

Moreover, since all are nonnegative,

as long as . It follows that is dominated by the genuine random walk , that is,

We can now obtain bounds on by analyzing hitting times of the random walk .

The subcritical case

Define the first time the comparison walk hits zero as

Since for , it is obvious that

Now we study . The intuition is that as , is a random walk with negative drift in the subcritical case . Thus , and in fact the hitting time has nice tails!

Lemma 2 Let and . Then for any positive integer ,

We will prove this lemma below. Using the lemma, we immediately obtain:

Corollary 3 If , then for any

Proof. Applying the Lemma 2 and the union bound,

This corollary proves part 1 of Theorem 1. In fact, it turns out that the constant is tight: by using the second moment method, one can prove a matching lower bound on (see, for example, the lecture notes by van der Hofstad), which implies that in fact in probability. The proof is not much more difficult, but we prefer to move on to the supercritical case.

Remark. It might seem somewhat surprising that the result we obtain is so sharp, considering that we have blindly replaced by the larger quantity . However, in going from to we do not lose as much as one might think at first sight. When is large and is relatively small, the excess term in the definition of is zero with high probability, as most vertices are unexplored and the Bernoulli success probability of the is very small. With a bit of work, one can show that and will actually stick together for times with probability going to one as . Thus, in the subcritical case where the random walk only lives for time steps, nothing is lost in going from to , and our rough intuition that should behave like a random walk as is vindicated.

To wrap up the subcritical case, it remains to prove the lemma.

Proof of Lemma 2. By the Markov inequality,

It remains to bound , which is a standard exercise in martingale theory.

Recall that

where are i.i.d. Define the moment generating function , and let

Since and is independent of ,

where we have used . So is a martingale.

In the case and ,

The inequality is by Fatou's lemma and the second equality is by the optional stopping theorem. To see the first equality, note that if , then and as , while if , then for all and . Thus .

Next, we compute . Recall that . It has the same distribution as the sum of i.i.d. variables. For , we have . Therefore,

where the last inequality is because for any . Now, by setting , we obtain that . Thus we have shown .

The supercritical case

The goal of the following lectures is to prove part 2 of Theorem 1. More precisely, we will prove:

Theorem 4 Let . Then

in probability, where is the smallest positive solution of the equation . Moreover, there is such that all but one of the components have size , with probability tending to as .

This theorem says that with probability tending to , there is a unique giant component whose size is , and all other components are small with size .

Here we provide some vague intuition for this theorem. When , the random walk satisfies , i.e., has positive drift. Then ! In fact, the further away it starts from , the smaller the probability it will ever hit . Consider the two situations:

• dies quickly: this implies that the component is small.
• lives long: then it must live very long, as once it gets far away from , the probability of returning is very small. This implies that the component must be very large (if we pretend that ).

Of course, is not (obviously eventually hits ). But the intuition explains that there cannot be components of intermediate size: given any vertex , either is small (), or it must get very large (, say). In fact, we will find that all components of size must grow all the way to . However, any pair of large components must intersect with high probability, as there are many potential edges between them! Therefore, all vertices with should be in the same giant component. We then show that the number of such vertices is with high probability.

Many thanks to Tracy Ke for scribing this lecture!

06. April 2013 by Ramon van Handel
Categories: Random graphs | Comments Off

## 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 lecture due to the ORFE/PACM colloquium of Elchanan Mossel.

The next Stochastic Analysis Seminar lecture will be on April 4. We will start fresh with a new topic: the study of the giant component of an Erdös-Rényi graph.

15. March 2013 by Ramon van Handel

## Lecture 3. Chromatic number

Let ${C}$ be set of integers that represent colors. A vertex coloring of a graph ${G=([n], E)}$ is an assignment ${c\,:\,\{1, \ldots, n\} \rightarrow C}$ of a color ${c(i) \in C}$ to each vertex ${i \in [n]}$. Furthermore a vertex coloring ${c}$ is said to be proper if ${c(i)\neq c(j)}$ for all ${(i,j) \in E}$. The chromatic number ${\chi(G)}$ of a graph ${G}$ is the smallest number ${|C|}$ of colors needed for a proper vertex coloring to exist. In this lecture, any coloring is a proper vertex coloring. All logs are in base ${2}$.

Theorem [Bollobas, 1988]
The chromatic number ${\chi(G)}$ of a random graph ${G\sim G(n,\frac12)}$ satisfies

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

1. Basic properties

In this section, we begin by reviewing some basic properties of the chromatic number, and in particular how it relates to independent sets. Recall that an independent set ${S \subset [n]}$ of a graph ${G=([n], E)}$ is a set of vertices such that ${i,j \in S \Rightarrow (i,j) \notin E}$. Independent sets are sometimes called stable sets. Denote by ${\bar G=([n], \bar E)}$ the complement graph of ${G}$ where ${(i,j) \in \bar E}$ iff ${(i,j) \notin E}$. If ${S}$ is an independent set of ${G}$, then it is a clique in ${\bar G}$. The largest independent set in ${G}$ is called independence number of ${G}$ and denoted by ${\alpha(G)}$.

Proposition For any graph ${G=([n],E)}$ with independence number ${\alpha(G)}$, clique number ${\omega(G)}$ and chromatic number ${\chi(G)}$ the following 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. Chromatic, clique and independence numbers

Our goal is to study the chromatic number of a random graph ${G \sim G(n,\frac12)}$. It actually builds upon the clique number that we studied during last lecture. Indeed, we will use the following observation: if ${G \sim G(n,\frac12)}$ then so does the complement graph ${\bar G}$ of ${G}$. It implies that the independence number ${\alpha(G)}$ has the same distribution as the clique number ${\omega(G)}$. We know from last lecture that ${\omega(G)=(2\log n)(1+o(1))}$. Therefore, it follows from the above proposition that

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

Our main theorem suggests that this simple bound is, in fact, tight. Proving this requires a stronger lower bound on clique of a random graph.

Define ${m=\lfloor n/\ln^2 n\rfloor}$ and let ${V \subset [n]}$ be a subset of ${|V|=m}$ vertices and observe that induced subgraph ${G_V=(V, E \cap [m]^2)}$ restricted to vertices in ${V}$ has distribution ${G(m,\frac12)}$.

Define

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

That is: every ${m}$ vertex subgraph contains an independent set of size ${\bar \alpha_m}$.

Consider now the following coloring procedure to produce a proper coloring. Pull out independent sets of size ${\bar \alpha_m}$ one by one and give each a distinct color. According to the definition of ${\bar \alpha_m}$, as long as there are at least ${m}$ vertices, this is possible. If there are less than ${m}$ vertices left, give each a distinct color.

The above algorithm gives one possible way of coloring graph ${G}$ and thus the output number is an upper bound on the chromatic number ${\chi(G)}$. Let us now compute this upper bound. By definition 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)$

Therefore, to find an upper bound on ${\chi(G)}$, we need to find a lower bound on ${\bar \alpha_m}$ for an appropriately chosen ${m}$. To that end, observe that

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

Therefore, we need to prove a bound on ${\mathbb{P}(\omega(G_{V}), uniformly in ${V}$. This can be done using concentration properties of a suitable martingale.

3. Azuma-Hoeffding inequality

Martingales have useful concentration properties. Specifically the following lemma holds.

Lemma [Azuma-Hoeffding inequality.]
Let ${(\Omega, \mathcal{F}, \{\mathcal{F}_i\}_{i \ge 0}, \mathbb{P})}$ be a filtered space and let ${X}$ be a random variable on ${(\Omega, \mathcal{F}, \mathbb{P})}$. Assume that the martingale ${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 positive integer ${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 following inequality due to Hoeffding. For any random variable ${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 Chernoff 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 displays 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 second part of the proof follows by applying the same argument to the martingale ${(-X_i)_{i\ge 0}}$. $\Box$

Consider the lexicographic ordering of ${[n]^2}$ and let ${E_1, \ldots, E_N \in \{0,1\}}$ be ${N={n \choose 2}}$ iid Bernoulli random variables with parameter ${1/2}$ indicating the presence of an edge in a graph ${G\sim G(n,\frac12)}$. Define the ${\sigma}$-algebra ${\mathcal{F}_i=\sigma(E_1, \ldots E_i), i=1, \ldots, N}$. We are going to apply the Azuma-Hoeffding inequality to the (Doob) martingale ${Y_i=\mathbb{E}[Y|\mathcal{F}_i]\,, \quad i=1, \ldots, N}$ where ${Y}$ is maximal number 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 disjoint ${k}$-clique. Moreover, this inequality would not hold if we had chosen ${Y}$ to be the number cliques of size ${k}$ (not necessarily disjoint). Indeed, adding or removing an edge can create or destroy many overlapping cliques.

It follows that,

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

Therefore, applying the Azuma-Hoeffding inequality, we get

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

It remains to show that ${\mathbb{E}[Y]}$ is sufficiently large. Note first that ${Y \ge X}$, where is ${Y}$ is the number 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 positive integers ${m}$ and

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

and let ${X}$ denote the number 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 asymptotic notation notations ${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 chosen later.

Moreover, 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 number 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\}.$

Moreover for any set ${S}$, let ${Z(S)}$ denote the number of ${k}$-cliques in ${G}$, other than ${S}$ itself, that share at least two vertices 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 following 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}$

Moreover, 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}$

Therefore,

$\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))\,.$

Moreover,

$\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 conclude the proof, observe that by Stirling, 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 therefore apply the previous proposition 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 completes the proof of our theorem.

Lecture and scribing by Philippe Rigollet

14. March 2013 by Philippe
Categories: Random graphs | Comments Off

## Lecture 2. Clique number

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

Theorem For the centered and normalized 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 number 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 number cannot be too big using a union bound. Then we show that the clique number cannot be too small using the second moment method. In the following, $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, choosing $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 second part it is useful to introduce some notation. 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 particular, ${\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 trivial observation 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 inequality. Note that by linearity of the expectation, ${\mathbb E} Y_k = {n \choose k} \left(\frac12\right)^{k\choose 2}$. Furthermore, 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 random variables 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 inequality ${{n \choose k} \geq \left(\frac{n}{k}\right)^k}$). Thus it remains to show that the following quantity 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 independence of the edges, for ${S, T}$ with ${|S \cap T| \leq 1}$ we have that ${X_S}$ and ${X_T}$ are independent, so that in the numerator of the above quantity one can restrict to ${S, T}$ with ${|S \cap T| \geq 2}$. Now by an elementary reasoning we have (with ${S_0}$ being an arbitrary subset 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 proving that the following quantity 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 rewritten 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 convex function 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 exponent in the above display 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 latter 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 infinity, concluding the proof. $\Box$

07. March 2013 by Sebastien Bubeck
Categories: Random graphs | Comments Off

## Time change for Spring 2013

Welcome to the stochastic analysis seminar blog! We are experimenting with this blog for the first time in the Spring 2013 semester. The intention is to post notes from the lectures here: we are grateful to several graduate students who have graciously volunteered to serve as scribes. In addition, any announcements or organizational matters will be posted to this blog. Information on previous semesters can be found here.

Time change: In order to avoid conflicts with a number of seminars, the stochastic analysis seminar will be held on Thursdays, 4:50-6:20, Bendheim Center 103 starting this week. That is, we start and end 20 minutes later than originally announced for the remainder of this semester.

05. March 2013 by Ramon van Handel

## Lecture 1. Introduction

There are many interesting models of random graphs, and there a lot of different questions that can be asked about them. In this seminar we will only have the time cover a few of the most classical results. The goal of this first lecture is to give an informal overview of what we intend to cover this semester.

What is a random graph?

Let ${G=(V,E)}$ be a graph, where ${V}$ is the set of vertices and ${E}$ is the set of edges (that is, a set of pairs of vertices). We will consider only simple graphs, that is, graphs with undirected edges and with no self-edges. The graph structure is compactly described by the incidence matrix ${H=(\eta_{ij})_{i,j\in V}}$, where ${\eta_{ij}=\mathbf{1}_{(i,j)\in E}}$. Thus ${\eta_{ii}=0}$ and ${\eta_{ij}=\eta_{ji}}$ for each ${i,j\in V}$.

Large, complex graphs and networks appear everywhere: the internet, social networks, etc.; and are often formed by some random process. One natural way to construct large complex graphs with interesting structure is to choose the incidence matrix randomly, which yields random graphs. Such models exhibit many fascinating probabilistic phenomena.

Erdös-Rényi graphs

Let ${G=(V,E)}$ be a random graph on ${|V|=n}$ vertices, such that ${(\eta_{ij})_{i is a collection of i.i.d. Bernoulli random variables with ${\mathbf{P}[\eta_{ij}=1]=p}$, ${\mathbf{P}[\eta_{ij}=0]=1-p}$. Such a random graph is called Erdös-Rényi graph, and we denote this model by ${G(n,p)}$.

The Erdös-Rényi graph is the simplest random graph model: for example, in a group of ${n}$ people, each pair are friends, independently, with probability ${p}$. Unfortunately, this is not a realistic model of most real-world networks. On the other hand, such models are used in engineering applications (for example in coding theory), and already the theory of this simple model is very rich and should be understood before more complicated models can be tackled. This model was the first systematically studied, albeit a slightly different form, by Erdös and Rényi in the late 1950s. More complicated models capture certain features of real-world graphs that are not well described by the Erdös-Rényi model, such as the small world and preferential attachment models; see the book by Durrett or the lecture notes by van der Hofstad, for example. Unfortunately, we will not have time to cover such models in this seminar.

The general question we will aim to address is: “What does a large Erdös-Rényi graph look like?” This question is rather vague. It turns out that there are two basic regimes in which different questions are of interest. In order to describe these two regimes, let us define the “complexity” of a graph ${G=(V,E)}$ as

$\displaystyle \mathrm{complexity}(G)=|E|-|V|+1.$

This definition is really intended for connected graphs, where it is a meaningful quantity.

For an Erdös-Rényi random graph ${G(n,p)}$ we have

$\displaystyle \mathbf{E}[\mathrm{complexity}(G(n,p))]=\binom{n}{2}p-n+1,$

since ${|E| = \sum_{i.  Of course, we do not know at this point whether the Erdös-Rényi graph is connected (this will be discussed below), but this formula can serve as an informal guide to motivate the two regimes of interest.

1. Fixed edge probability. Fix ${p\in(0,1)}$ and let ${n}$ go to infinity. We expect such a graph to be very dense: on average, a fraction ${p}$ of all possible edges is present, and each vertex is connected with ${(n-1)p}$ other vertices. In this regime the expected complexity of the graph blows up, that is, ${\mathbf{E}[\mathrm{complexity}(G(n,p))] \sim n^2 \rightarrow \infty}$. So, we have to choose questions to study that are interesting for a dense graph where the structure is rich: we need a “rich” way of measuring properties in this regime.
2. Low complexity. Take ${p \sim \frac{c}{n}}$ for some ${c>0}$ and let ${n}$ go to infinity. This is the largest edge probability that we can take so that the expected complexity of the graph does not blow up, since the number of edges and the number of vertices are of the same order. In this regime we get different behavior of the graphs depending on the value of ${c}$.

Clearly, the random graphs in regimes 1 and 2 will look quite different.

Regime 1: Fixed edge probability

In this regime the graph is very rich. What questions are meaningful? Heuristically, a rich graph must contain interesting subgraphs, and must possess a complex combinatorial structure. We now state two results in this spirit that we are going to prove in the following lectures. The proofs of these results are nice examples of use of the probabilistic method.

Clique number. A clique in a graph ${G=(V,E)}$ is a complete subgraph, that is, a subset ${W\subseteq V}$ such that ${(i,j)\in E}$ for every ${i,j\in W}$, ${i\neq j}$. If ${G}$ describes friendships, a clique is a group of mutual friends. Intuitively, a rich graph must contain a large clique. The clique number ${\omega(G)}$ is the cardinality of the largest clique in ${G}$.

Theorem 1 Let ${G(n,p)}$ be an Erdös-Rényi graph. Then

$\displaystyle \frac{\omega(G(n,\frac{1}{2}))}{2 \log_2 n} \overset{n\rightarrow \infty}{\longrightarrow} 1\quad\text{in probability}.$

On a heuristic level, we see that this result makes sense since

$\mathbf{E}[\mathrm{number~of~cliques~of~size~}k] = \binom{n}{k}\left(\frac{1}{2}\right)^{\binom{k}{2}} \sim n^k 2^{-k^2/2} = 2^{k \log_2 n - k^2/2},$

from which we see that ${k\sim 2 \log_2 n}$ is the critical case. Of course, one could also study similar questions for other types of subgraphs, but we will not do that.

Chromatic number. A coloring of ${(V,E)}$ is a color assignment to each vertex in ${V}$ such that for each ${(i,j)\in E}$, ${i}$ and ${j}$ have a different color. The chromatic number ${\chi(G)}$ is the smallest number of colors needed to color ${G}$. It is clear that the chromatic number of a graph tells us something about the complexity of the graph.

Theorem 2 Let ${G(n,p)}$ be an Erdös-Rényi graph. Then

$\displaystyle \frac{\chi(G(n,\frac{1}{2}))}{n/ (2 \log_2 n)} \overset{n\rightarrow \infty}{\longrightarrow} 1\quad\text{in probability}.$

So, in the Erdös-Rényi graph the chromatic number grows as ${n/ (2 \log_2 n)}$, smaller than in a complete graph were the chromatic number is ${n}$, but much larger than in trees which can be colored with only 2 colors regardless of their size. That the same factor ${2 \log_2 n}$ appears in both theorems above is not a coincidence: there is a relation between clique number and chromatic number that forms the basis for the proof.

Regime 2: Low complexity

In this regime we consider the case ${p\sim \frac{c}{n}}$, so each vertex has ${c}$ neighbors on average:

$\mathbf{E}[\mathrm{number~of~neighbors~of~}v] = \frac{c}{n} (n-1) \sim c.$

In this case we expect the graph to be much simpler than in the previous regime. If ${c}$ is small, for example, we expect the graph to be very disconnected, with a lot of small connected pieces. It turns out that this can be made precise. The following is a somewhat informal statement of a theorem that we will prove in detail in the following lectures.

“Theorem” 3 For ${v\in V}$, let ${C_v}$ be the connected component of ${G(n,\frac{c}{n})}$ that contains ${v}$.

1. If ${c<1}$, then ${\max_{v\in V} |C_v| \approx \log n}$.
2. If ${c>1}$, then ${\max_{v\in V} |C_v| \approx n}$ and all other components have size ${\lesssim\log n}$.
3. If ${c=1}$, then ${\max_{v\in V} |C_v| \approx n^{2/3}}$ and there are several large components.

Moreover, all ${C_v}$ with ${|C_v| \lesssim \log n}$ are either trees or have one cycle with high probability.

So, ${G(n,\frac{c}{n})}$ decomposes into many disconnected, simple pieces in the subcritical case ${c<1}$. In the supercritical case ${c>1}$ we get emergence of one giant component that is complex, with some remaining disconnected simple pieces. The critical case ${c=0}$ is the most complicated. In this case there are additional phase transitions near the critical window ${p\sim \frac{1}{n} \pm \frac{c}{n^{4/3}}}$, with non trivial limit distribution for the component sizes and complexities. [Note that in all these cases the Erdös-Rényi graph will have multiple connected components; the threshold for the entire graph to be connected turns out to be $p\sim\frac{\log n}{n}$.]

How do we prove such a theorem? We will use a dynamical method: start at ${v}$, then explore ${C_v}$ step by step much as in a game of Minesweeper. We then analyze the hitting times of this “random walk”. One can also study Brownian scaling limits of such random walks, which provides a mechanism to define “infinite limiting objects” in this theory.

Many thanks to Patrick Rebeschini for scribing this lecture!

01. March 2013 by Ramon van Handel
Categories: Random graphs | Comments Off

## Spring 2013: Random graphs

Complex graphs and networks are ubiquitous throughout science and engineering, and possess beautiful mathematical properties. The goal of these informal lectures is to provide an introduction to some of the most basic results in the theory of (Erdos-Renyi) random graphs from the probabilistic viewpoint: chromatic number and clique number, and the size of the largest component in the subcritical, supercritical, and critical regimes. If time permits, we will discuss Brownian limits.

Prerequisites: Probability at the level of ORF 526 is assumed.

Time and location: Thursdays, 4:50-6:20, Bendheim Center room 103.
The first lecture will be on February 28.
There will be no lecture on March 28 (colloquium).

References:

25. February 2013 by Ramon van Handel
Categories: Random graphs | Comments Off