Lecture 5. Giant component (2)

Consider the Erdös-Rényi graph model G(n,\frac{c}{n}), and denote as usual by C_v the connected component of the graph that contains the vertex v. In the last lecture, we focused mostly on the subcritical case c < 1, where we showed that \max_v|C_v|\lesssim\log n. Today we will begin developing the supercritical case c > 1, where \max_v|C_v| \sim (1-\rho)n for a suitable constant 0<\rho<1. In particular, our aim for this and next lecture is to prove the following theorem.

Theorem. Let c>1. Then

    \[\frac{\max_v|C_v|}{n}\xrightarrow{n\to\infty} 1 - \rho 	\quad\mbox{in probability},\]

where \rho is the smallest positive solution of the equation \rho = e^{c(\rho-1)}. Moreover, there is a \beta>0 such that all but one of the components have size \leq \beta\log n with probability tending to 1 as n\to\infty.

Beginning of the proof. Define the set

    \[K = \{ v: |C_v| > \beta \log n\}.\]

The proof of the Theorem consists of two main parts:

  • Part 1: \mathbb{P}[C_v = C_{v'}~ \forall v,v' \in K] \xrightarrow{n \to \infty} 1.
  • Part 2: \frac{|K|}{n} \xrightarrow{n \to \infty} 1-\rho 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 \rho 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 K is itself a connected component. Indeed, if v\in K and v'\not\in K then v,v' must lie in disjoint connected components by the definition of K. On the other hand, with probability tending to one, all v,v'\in K must lie in the same connected component by Part 1. Therefore, with probability tending to one, the set K forms a single connected component of the graph. By Part 2, the size of this component is \sim (1-\rho)n, while by the definition of K, all other components have size \le \beta\log n. This completes the proof. \quad\square

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. \mathbb{E}\big[\frac{|K|}{n}\big] \xrightarrow{n\to\infty} 1-\rho.
  2. \mathrm{Var}\big[\frac{|K|}{n}\big] \xrightarrow{n\to\infty}0.

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:

    \[\mathbb{E}\bigg[\frac{|K|}{n}\bigg] =  	\mathbb{E}\Bigg[ 	\frac{1}{n} \sum_{v \in [n]}  	\mathbf{1}_{|C_v|>\beta\log n} 	\Bigg] =  	\frac{1}{n} \sum_{v \in [n]}  	\mathbb{P}[\left|C_v\right| > \beta \log n ] = 	\mathbb{P}[\left|C_v\right| > \beta \log n ],\]

where we note that \mathbb{P}[\left|C_v\right| > \beta \log n ] does not depend on the vertex v 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

    \[\mathbb{P}[\left|C_v\right| \le \beta \log n ] 	\xrightarrow{n\to\infty}\rho.\]

This is what we will now set out to accomplish.

In the previous lecture we defined exploration process (U_t, A_t, R_t). We showed that

    \[|C_v| = \tau := \inf \{t: |A_t| = 0\}\]

and that for t<\tau

    \[|A_{t+1}| = |A_t| - 1 + \sum_{w \in U_t} \eta_{wi_t}, 	\qquad |A_0|=1,\]

where i_t \in A_t is an arbitrary nonanticipating choice, say, i_t = \min A_t (recall that (\eta_{ij})_{i,j\in[n]} denotes the adjacency matrix of the random graph). As \eta_{ij} are i.i.d. \mathrm{Bernoulli}(\frac{c}{n}) and as edges emanating from the set of unexplored vertices U_t have not yet appeared in previous steps, the process |A_t| is “almost'' a random walk: it fails to be a random walk as we only add |U_t| Bernoulli variables in each iteration, rather than a constant number. In the last lecture, we noted that we can estimate |A_t| from above by a genuine random walk S_t by adding some fictitious vertices. To be precise, we define

    \[S_{t+1}=S_t - 1 + \sum_{w\in U_t} \eta_{wi_t} + 	\sum_{w=1}^{n-|U_t|}\tilde\eta_w^t,\qquad S_0=1,\]

where \tilde\eta_w^t are i.i.d. \mathrm{Bernoulli}(\frac{c}{n}) independent of the \eta_{ij} (if t\ge\tau, then A_t=\varnothing and thus i_t is undefined; in this case, we simply add all n variables \tilde\eta_w^t). In the present lecture, we also need to bound |A_t| from below. To this end, we introduce another process \bar S_t as follows:

    \[\bar S_{t+1}=\left\{ 	\begin{array}{ll} 	\bar S_t - 1 + \sum_{w\in U_t} \eta_{wi_t} + 		\sum_{w=1}^{n-\beta\log n-|U_t|}\tilde\eta_w^t 	& \mbox{if }|U_t|< n-\beta\log n,\\ 	\bar S_t - 1 + \sum_{w\in \bar U_t} \eta_{wi_t} 	& \mbox{if }|U_t|\ge n-\beta\log n, 	\end{array}\right. 	\qquad \bar S_0=1,\]

where \bar U_t is the set consisting of the first n-\beta\log n elements of U_t in increasing order of the vertices (if t\ge\tau, we add n-\beta\log n variables \tilde\eta_w^t). The idea behind these processes is that S_t is engineered, by including “fictitious'' vertices, to always add n i.i.d. Bernoulli variables in every iteration, while \bar S_t is engineered, by including “fictitious'' vertices when |U_t| is small and omitting vertices when |U_t| is large, to always add n-\beta\log n i.i.d. Bernoulli variables in every iteration. The following facts are immediate:

  • S_t is a random walk with i.i.d. \mathrm{Binomial}(n,\frac{c}{n})-1 increments.
  • \bar S_t is a random walk with i.i.d. \mathrm{Binomial}(n-\beta\log n,\frac{c}{n})-1 increments.
  • S_t\ge |A_t| for all t\le\tau.
  • \bar S_t\le |A_t| for all t\le\tau on the event \{|C_v|\le\beta\log n\}.

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

We now define the hitting times

    \[T = \inf\{t:S_t=0\},\qquad 	\bar T = \inf\{t:\bar S_t=0\}.\]

Then we evidently have

    \[\mathbb{P}[T \le \beta \log n] \le  	\mathbb{P}[|C_v| \le \beta \log n] \le  	\mathbb{P}[\bar T \le \beta \log n].\]

(Note how we cleverly chose the random walk \bar S_t precisely so that \bar T\le |C_v| whenever |C_v|\le \beta\log n). We have therefore reduced the problem of computing \mathbb{P}[|C_v| \le \beta \log n] 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 S_t and \bar S_t have increments distributed as \mathrm{Binomial}(n,\frac{c}{n})-1 and \mathrm{Binomial}(n-\beta\log n,\frac{c}{n})-1, respectively. As n\to\infty, both increment distributions converge to a \mathrm{Poisson}(c)-1 distribution, so we expect that \mathbb{P}[|C_v|\le\beta\log n]\sim\mathbb{P}[T_0\le\beta\log n] where T_0 is the first hitting time of the Poisson random walk. On the other hand, as \mathbb{P}[T_0\le\beta\log n] \to \mathbb{P}[T_0<\infty], we expect that \mathbb{P}[|C_v|\le\beta\log n]\to \mathbb{P}[T_0<\infty]. 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 \rho=\mathbb{P}[T_0<\infty] comes from!

We now proceed to make this intuition precise. First, we show that the probability \mathbb{P}[T<\beta\log n] can indeed be replaced by \mathbb{P}[T<\infty], as one might expect.

Lemma. \mathbb{P}[T \le \beta \log n] = \mathbb{P}[T < \infty] - o(1) as n\to\infty.

Proof. We need to show that

    \[\mathbb{P} [\beta \log n < T < \infty] \xrightarrow{n \to \infty} 0.\]

Note that as S_T=0 when T<\infty,

    \[\mathbb{P}[k \le T < \infty] = \sum_{t=k}^{\infty}  	\mathbb{P}[T=t] \le \sum_{t=k}^{\infty} \mathbb{P}[S_t = 0].\]

We can evidently write

    \[\mathbb{P}[S_t = 0] =  	\mathbb{E}[\mathbf{1}_{S_t=0} e^{\gamma S_t} ]  	\le  	\mathbb{E} [e^{\gamma S_t}] =  	e^{\gamma} \mathbb{E}[e^{\gamma X_1}]^t\]

where S_t - S_{t-1} =: X_t \sim \mathrm{Binomial}(n,\frac{c}{n})-1 and

    \[\mathbb{E} [e^{\gamma X_1}] = e^{-\gamma}  	(1+\tfrac{c}{n}(e^{\gamma}-1))^n  	\le e^{c(e^{\gamma}-1)-\gamma}.\]

Choosing \gamma = -\log c, we obtain \mathbb{E} [e^{\gamma X_1}] \le e^{1-c + \log c} < 1 for c \ne 1. Therefore,

    \[\mathbb{P} [\beta\log n < T < \infty] \le  	\frac{1}{c} \sum_{t=\beta\log n}^{\infty}  	e^{(1-c + \log c)t} 	\xrightarrow{n\to\infty}0.\]

This completes the proof. \qquad\square

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

    \[\mathbb{P} [T< \infty] - o(1) \le  	\mathbb{P}[|C_v| \le \beta \log n] \le \mathbb{P}[\bar T < \infty].\]

To complete computation of the mean size of the giant component, it therefore remains to show that \mathbb{P} [T<\infty] and \mathbb{P}[\bar T<\infty] converge to \rho. In fact, we can compute these quantities exactly.

Lemma. Let c>1, \frac{c}{n} < 1. Then

    \[\mathbb{P} [T<\infty] = \rho_n\]

where \rho_n is the smallest positive solution of \rho_n = (1+\frac{c}{n}(\rho_n-1))^n.

Proof. Recall the martingale M_t used in last lecture:

    \[M_t = e^{\gamma S_t - \phi(\gamma)t}, 	\qquad 	\phi(\gamma)=\log \mathbb{E}[e^{\gamma X_1}] = 	\log\big[e^{-\gamma}(1+\tfrac{c}{n}(e^{\gamma}-1))^n\big].\]

Suppose that \gamma < 0 and \phi(\gamma) > 0. Then

    \[\mathbb{E} [e^{-\phi(\gamma)T}] =  	\mathbb{E} \Big[\lim_{k \to \infty} M_{k \wedge T}\Big]  	= \lim_{k \to \infty} \mathbb{E} [M_{k \wedge T}] = M_0 = e^{\gamma}.\]

The first equality holds since if T < \infty then S_T = 0 and M_{k \wedge T} \to M_T = e^{-\phi(\gamma)T}, while if T = \infty then S_{k} \ge 0 and M_k \to 0 = e^{-\phi(\gamma)T}. The second equality holds by dominated convergence since 0 \le M_{k \wedge T} \le 1, and the third equality is by the optional stopping theorem.

Now suppose we can find \gamma_n < 0 such that \phi(\gamma) \downarrow 0 as \gamma \uparrow \gamma_n. Then we have

    \[\rho_n := 	e^{\gamma_n} = \lim_{\gamma \uparrow \gamma_n}  	\mathbb{E}[e^{-\phi(\gamma)T}] = 	\mathbb{E} \Big[\lim_{\gamma \uparrow \gamma_n} e^{-\phi(\gamma)T}\Big]  	= \mathbb{P}[T < \infty]\]

by dominated convergence. Thus, evidently, it suffices to find \gamma_n with the requisite properties. Now note that as \phi(\gamma_n)=0, \gamma_n<0, and \phi(\gamma)>0 for \gamma<\gamma_n, we evidently must have

    \[\rho_n = (1+\tfrac{c}{n}(\rho_n-1))^n,\qquad 	\rho_n < 1,\qquad 	\rho < (1+\tfrac{c}{n}(\rho-1))^n \mbox{ for }\rho<\rho_n.\]

We can find such \rho_n by inspecting the following illustration:

Rendered by QuickLaTeX.com

Evidently the requisite assumptions are satisfied when \rho_n is the smallest root of the equation \rho_n=(1+\tfrac{c}{n}(\rho_n-1))^n (but not for the larger root at 1!) \quad\square

Remark. Note that the supercritical case c>1 is essential here. If c\le 1 then the equation for \rho_n has no solutions <1, and the argument in the proof does not work. In fact, when c\le 1, we have \mathbb{P}[T<\infty]=1.

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

    \[\mathbb{P}[\bar T < \infty] = \bar \rho_n\]

where \bar\rho_n is the smallest positive solution of \bar \rho_n = (1+\frac{c}{n}(\bar \rho_n-1))^{n-\beta \log n}. Letting n\to\infty, we see that

    \[\lim_{n \to \infty} \mathbb{P}[|C_v|\le\beta\log n] =  	\lim_{n \to \infty} \mathbb{P}[T<\infty] =  	\lim_{n \to \infty} \mathbb{P}[\bar T<\infty] = \rho,\]

where \rho is the smallest solution of the equation \rho=e^{c(\rho-1)} (which is precisely the probability that the Poisson random walk hits zero, by the identical proof to the lemma above). We have therefore proved

    \[\mathbb{E}\bigg[\frac{|K|}{n}\bigg] \xrightarrow{n\to\infty} 1-\rho.\]

Variance of the giant component size

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

    \[\mathrm{Var}\bigg[\frac{|K|}{n}\bigg] = 	\mathrm{Var}\bigg[1-\frac{|K|}{n}\bigg]  	\xrightarrow{n\to\infty} 0.\]

To this end, let us consider

    \[\mathbb{E}\bigg[\bigg(1-\frac{|K|}{n}\bigg)^2\bigg] = 	\mathbb{E}\bigg[\bigg(\frac{1}{n} \sum_{v \in [n]}  		\mathbf{1}_{|C_v| \le \beta \log n}\bigg)^2\bigg] =  	\frac{1}{n^2} \sum_{v,w \in [n]}  	\mathbb{P}[|C_v| \le \beta \log n, |C_w| \le \beta \log n].\]

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

    \[\begin{array}{lcl} 	\mathbb{P}[|C_v| \le \beta \log n, |C_w| \le \beta \log n] 	&=& 	\mathbb{E}[ 	\,\mathbb{P}[|C_v| \le \beta \log n|C_w]\, 	\mathbf{1}_{|C_w| \le \beta \log n}\,] \\ 	&=& 	\sum_{I \subseteq [n], |I| \le \beta\log(n)}  	\mathbb{P}[C_w = I]\, \mathbb{P}[|C_v| \le \beta\log n|C_w = I]. 	\end{array}\]

To proceed, note that the event \{C_w=I\} can be written as

    \[\{C_w=I\} = \{(\eta_{ij})_{i,j\in I}\mbox{ defines a connected  	subgraph and }\eta_{ij}=0\mbox{ when }i\in I,~j\not\in I\}.\]

In particular, the event \{C_w=I\} is independent of the edges \eta_{ij} for i,j\not\in I. Therefore, for v\not\in I, the conditional law of C_v given C_w=I coincides with the (unconditional) law of C_v^{[n]\backslash I}, the conncted component containing v in the induced subgraph on the vertices [n]\backslash I:

    \[\mathbb{P}[|C_v| \le \beta\log n|C_w = I] = 	\mathbb{P}[|C_v^{[n]\backslash I}|\le \beta\log n]\qquad 	\mbox{for }v\not\in I.\]

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

    \[\mathbb{P}[|C_v| \le \beta\log n|C_w = I] = 	\mathbb{P}[|C_1^{[n-|I|]}|\le \beta\log n] \le 	\mathbb{P}[|C_1^{[n-\beta\log n]}|\le \beta\log n]\]

for v\not\in I, |I|\le\beta\log n. In particular, we obtain

    \[\sum_{v,w\in[n]} 	\mathbb{P}[|C_v| \le \beta \log n, |C_w| \le \beta \log n] 	\le 	\mathbb{E}[n-|K|]\,\{ 	\beta\log n + n\, \mathbb{P}[|C_1^{[n-\beta\log n]}|\le \beta\log n]\}.\]

Now note that, by its definition, C_1^{[k]} is distributed precisely as the component containing vertex 1 in the G(k,\frac{c}{n}) random graph model. We can therefore show, repeating exactly the proof of the mean size of the giant component above, that

    \[\mathbb{P}[|C_1^{[n-\beta\log n]}|\le \beta\log n] = 	\rho + o(1) =  	\mathbf{E}\bigg[1-\frac{|K|}{n}\bigg] + o(1).\]

We have therefore shown that

    \[\mathbb{E}\bigg[\bigg(1-\frac{|K|}{n}\bigg)^2\bigg] = 	\frac{1}{n^2}\sum_{v,w\in[n]}  	\mathbb{P}[|C_v| \le \beta \log n, |C_w| \le \beta \log n] 	\le 	\mathbf{E}\bigg[1-\frac{|K|}{n}\bigg]^2+o(1),\]

which evidently implies

    \[\mathrm{Var}\bigg[1-\frac{|K|}{n}\bigg] \le o(1).\]

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 \beta, or even on the \beta\log n rate, in the definition of the set K: 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 \sim 1 or \sim n. We find out only in the next lecture why the rate \beta\log n (for \beta sufficiently large!) is important: only sufficiently large connected components are guaranteed to intersect, while there might (and do) exist components of order \sim\log n 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 G(n,p). In previous lectures, we focused on the “high complexity regime”, i.e., as n goes to infinity, p is fixed. We discussed topics such as clique numbers and chromatic numbers. From now on, we shall consider the “low complexity regime”, where as n goes to infinity, p=\frac{c}{n} for a fixed constant c>0. As before, let \eta=(\eta_{i,j})_{i,j\in[n]} be the adjacency matrix of G(n, \frac{c}{n}). Then \{\eta_{ij}: i,j\in[n], i<j\} are i.i.d. Bernoulli random variables with success probability p=\frac{c}{n}.

Theorem 1 Let C_v be the connected component of G(n, \frac{c}{n}) that contains v\in [n].

  1. If c<1, then \max_v|C_v|= O(\log n) in probability.
  2. If c>1, then \max_v|C_v|\sim (1-\rho) n in probability, for some 0<\rho<1.
  3. If c=1, then \max_v|C_v|\sim n^{2/3} in distribution.

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

The exploration process

How to study |C_v|? We will explore C_v by starting an “exploration process'' at v that moves around C_v 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 C_v is exactly |C_v|. As a consequence, studying |C_v| reduces to studying a hitting time of a certain random walk, and to the latter we can apply martingale theory.

At each time t=0,1,2,\ldots, we maintain three sets of vertices:

    \begin{eqnarray*} 	R_t &=& \{\text{removed sites}\},\\ 	A_t &=& \{\text{active sites}\},\\  	U_t &=& \{\text{unexplored sites}\}. \end{eqnarray*}

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

  • At t=0, initialize A_0=\{v\}, U_0=[n]\backslash \{v\} and R_0=\varnothing. Namely, only v is active, all the vertices other than v are unexplored, and no vertices have been removed.

    Rendered by QuickLaTeX.com

  • At t=1, update A_1=A_0\backslash \{v\}\cup \{\text{neighbors of } v\}, U_1=U_0\backslash A_1 and R_1=\{v\}. Namely, all neighbors of v are moved from the unexplored set to the active set, and v itself is removed.

    Rendered by QuickLaTeX.com

  • At t=2, pick some x\in A_1 and update A_2=A_1\backslash \{x\}\cup \{\text{unexplored neighbors of } x\}, U_2=U_1\backslash A_2 and R_2=R_1\cup \{x\}. Namely, all unexplored neighbors of x are moved into the active set, and x itself is removed.

    Rendered by QuickLaTeX.com

  • At time t, we pick some vertex x from the current active set A_{t-1}, activate all unexplored neighbors of x and remove x itself.

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

A formal description of the “exploration process'':

  • Initialize A_0=\{v\}, U_0=[n]\backslash \{v\} and R_0=\varnothing.
  • For t\geq 0, we set

        \begin{eqnarray*} 	R_{t+1} &=& R_t\cup \{i_t\},\\ 	A_{t+1} &=& A_t\backslash \{i_t\}\cup \{w\in U_t: \eta_{wi_t}=1\},\\ 	U_{t+1} &=& U_t\backslash \{w\in U_t: \eta_{wi_t}=1\}, \end{eqnarray*}

    where i_t\in A_t is a nonanticipating but otherwise arbitrary choice.

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

    \[ \tau\equiv \inf\{t: |A_t|=0 \} = |C_v|. \]

So, we only need to study the stopping time \tau.

Recall that \eta_{ij} indicates whether there is an edge between vertices i and j, and \eta_{ij}\overset{\mathrm{i.i.d.}}{\sim} \text{Bernoulli}(\frac{c}{n}). By construction,

    \[ |A_{t+1}| = |A_t| - 1 + \sum_{w\in U_t} \eta_{wi_t}. \]

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 i_t are unvisited still (note that when n is really large and t is relatively small, this assumption makes sense). Then |A_{t+1}|-|A_t|+1 is the sum of n independent \text{Bernoulli}(\frac{c}{n}) variables, which has a \text{Binomial}(n, \frac{c}{n}) distribution. This binomial variable is independent of the past because it only depends on unexplored edges; in addition, its distribution does not depend on |A_t|. Therefore, |A_t| would be a random walk with increment distribution \text{Binomial}(n, \frac{c}{n})-1\approx\text{Poisson}(c)-1. Then, studying |C_v| 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 n\to\infty and will serve as a guiding principle for the proof.

A comparison random walk

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

Let \tilde{\eta}_{v}^t be i.i.d. \text{Bernoulli}(\frac{c}{n}) for t\geq 0, v\in[n], which are independent of (\eta_{ij}). Define

    \[ 	S_0 = 1, \qquad S_{t+1} = S_t - 1 +  	\sum_{w\in U_t}  	\eta_{wi_t} + \sum_{w\in [n]\backslash  	U_t}\tilde{\eta}^t_{w}. \]

(When t\ge\tau, then A_t=\varnothing and thus i_t is undefined; in this case, we simply add all n variables \tilde\eta^t_w.)
Note that \sum_{w\in U_t} \eta_{wi_t} is the sum of edges from A_t to U_t. Since we have not explored U_t yet, those edges are independent of all edges explored up to time t (here we use that i_t is nonanticipating). We therefore see that (S_t) is indeed a random walk with increment

    \[ S_{t}- S_{t-1} \sim \text{Binomial}(n, \tfrac{c}{n})-1. \]

Moreover, since all \tilde{\eta}_{w}^t are nonnegative,

    \[ S_{t+1} - S_t \geq |A_{t+1}| - |A_t| \]

as long as t<\tau. It follows that |A_t| is dominated by the genuine random walk S_t, that is,

    \[|A_t| \le S_t \quad\mbox{for all }t\le \tau.\]

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

The subcritical case c<1

Define the first time the comparison walk hits zero as

    \[T\equiv\inf\{t: S_t=0\}.\]

Since |A_t|\leq S_t for t\le\tau, it is obvious that

    \[|C_v|=\tau\leq T.\]

Now we study T. The intuition is that as \mathbb{E}[S_{t+1}-S_t]=c-1, (S_t) is a random walk with negative drift in the subcritical case c<1. Thus \mathbb{P}[T<\infty]=1, and in fact the hitting time T has nice tails!

Lemma 2 Let c<1 and \alpha=c-1-\log c>0. Then for any positive integer k,

    \[ \mathbb{P}[T\geq k]\leq \frac{1}{c} e^{-\alpha k}. \]

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

Corollary 3 If c<1, then for any a>\frac{1}{\alpha}=\frac{1}{c-1-\log c}

    \[ \mathbb{P}\big[\max_v|C_v|\geq a\log n\big] \xrightarrow{n\to\infty} 0.  \]

Proof. Applying the Lemma 2 and the union bound,

    \begin{eqnarray*} \mathbb{P}\big[\max_v|C_v|\geq a\log n\big] &\leq & \sum_{v\in[n]} \mathbb{P}[|C_v|\geq a\log n]\\ &\leq & \sum_{v\in[n]} \mathbb{P}[T\geq a\log n] \\ &\leq & \frac{n}{c} n^{-a\alpha} \to 0. \qquad\square \end{eqnarray*}

This corollary proves part 1 of Theorem 1. In fact, it turns out that the constant \frac{1}{\alpha} is tight: by using the second moment method, one can prove a matching lower bound on \max_v|C_v| (see, for example, the lecture notes by van der Hofstad), which implies that in fact \max_v|C_v|\sim \frac{1}{\alpha}\log n 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 |A_t| by the larger quantity S_t. However, in going from |A_t| to S_t we do not lose as much as one might think at first sight. When n is large and t is relatively small, the excess term \sum_{w\in[n]\backslash U_t}\tilde{\eta}^t_w in the definition of S_t is zero with high probability, as most vertices are unexplored and the Bernoulli success probability \frac{c}{n} of the \tilde{\eta}^t_w is very small. With a bit of work, one can show that S_t and |A_t| will actually stick together for times t\lesssim\log n with probability going to one as n\to\infty. Thus, in the subcritical case where the random walk only lives for \sim\log n time steps, nothing is lost in going from |A_t| to S_t, and our rough intuition that |A_t| should behave like a random walk as n\to\infty is vindicated.

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

Proof of Lemma 2. By the Markov inequality,

    \[ \mathbb{P}[T\geq k] = \mathbb{P}[e^{\alpha T}\geq e^{\alpha k}] \leq e^{-\alpha k} \mathbb{E}[e^{\alpha T}].  \]

It remains to bound \mathbb{E}[e^{\alpha T}]\le\frac{1}{c}, which is a standard exercise in martingale theory.

Recall that

    \[S_t = 1+\sum_{k=1}^t X_k,\]

where X_k are i.i.d. Define the moment generating function \phi(\beta)= \log\mathbb{E}[e^{\beta X_k}], and let

    \[ M_t \equiv e^{\beta S_t-\phi(\beta)t}, \qquad \text{for }t\geq 0.  \]

Since e^{\beta S_t}= e^{\beta}\prod_{k=1}^t e^{\beta X_k} and X_t is independent of M_0,M_1,\cdots,M_{t-1},

    \[ 	\mathbb{E}[M_t|M_0,\cdots, M_{t-1}] = M_{t-1}\, 	\mathbb{E}[\tfrac{M_t}{M_{t-1}}|M_0,\cdots, M_{t-1}]  	= M_{t-1}\, \mathbb{E}[e^{\beta X_t-\phi(\beta)}] = M_{t-1}, \]

where we have used \mathbb{E}[e^{\beta X_k - \phi(\beta)}]=1. So (M_t) is a martingale.

In the case \beta>0 and \phi(\beta)<0,

    \[\mathbb{E}[e^{-\phi(\beta)T}] = \mathbb{E}\big[\lim_{n\to\infty} M_{T\wedge n}\big] \leq\liminf_{n\to\infty} \mathbb{E}[M_{T\wedge n}]= M_0 = e^{\beta}.\]

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 T<\infty, then S_{T\wedge n}\to S_T=0 and T\wedge n\to T as n\to\infty, while if T=\infty, then S_{T\wedge n}>0 for all n and T\wedge n\to\infty. Thus e^{-\phi(\beta)T}=\lim_{n\to\infty}e^{\beta S_{T\wedge n}-\phi(\beta)(T\wedge n)}=\lim_{n\to\infty}M_{T\wedge n}.

Next, we compute \phi(\beta). Recall that (X_k+1)\sim \text{Binomial}(n, \frac{c}{n}). It has the same distribution as the sum of n i.i.d. \text{Bernoulli}(\frac{c}{n}) variables. For Y\sim\text{Bernoulli}(p), we have \mathbb{E}[e^{\beta Y}]= 1+(e^{\beta}-1)p. Therefore,

    \begin{eqnarray*} -\phi(\beta) &=& - \log \mathbb{E}[e^{\beta X_t}]\\ &=& -\log\big( e^{-\beta} (1+(e^{\beta}-1)\tfrac{c}{n})^n \big)\\ &=& \beta - n\log\big(1+(e^{\beta}-1)\tfrac{c}{n}\big)\\ &\geq& \beta - c(e^{\beta}-1), \end{eqnarray*}

where the last inequality is because -\log(1+x)\geq -x for any x. Now, by setting \beta=-\log c, we obtain that -\phi(\beta)\geq c-1-\log c=\alpha. Thus we have shown \mathbb{E}[e^{\alpha T}]\le\mathbb{E}[e^{-\phi(\beta)T}]\le e^\beta=\frac{1}{c}. \quad\square

The supercritical case c>1

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

Theorem 4 Let c>1. Then

    \[ \frac{\max_v|C_v|}{n}\xrightarrow{n\to\infty} 1 - \rho \]

in probability, where \rho is the smallest positive solution of the equation \rho = e^{c(\rho-1)}. Moreover, there is \beta>0 such that all but one of the components have size \leq \beta\log n, with probability tending to 1 as n\to\infty.

This theorem says that with probability tending to 1, there is a unique giant component whose size is (1-\rho)n, and all other components are small with size \leq \beta\log n.

Here we provide some vague intuition for this theorem. When c>1, the random walk (S_t) satisfies \mathbb{E}[S_t-S_{t-1}]=c-1>0, i.e., (S_t) has positive drift. Then \mathbb{P}[T<\infty]<1! In fact, the further away it starts from 0, the smaller the probability it will ever hit 0. Consider the two situations:

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

Of course, S_t is not |A_t| (obviously |A_t| eventually hits 0). But the intuition explains that there cannot be components of intermediate size: given any vertex v, either |C_v| is small (\lesssim \log n), or it must get very large (\gtrsim n^{2/3}, say). In fact, we will find that all components of size \geq \beta\log n must grow all the way to \gtrsim n^{2/3}. However, any pair of large components must intersect with high probability, as there are many potential edges between them! Therefore, all vertices v with |C_v|\geq \beta\log n should be in the same giant component. We then show that the number of such vertices is (1-\rho)n 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
Categories: Announcement | Comments Off

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<k)&\le& \sum_{\substack{V\subset [n]\\ |V|=m}} \mathbb{P}(\alpha(G_{V})<k)\\ &\le& {n \choose m} \max_{\substack{V\subset [n]\\ |V|=m}}\mathbb{P}(\omega(G_{V})<k)\,. \end{array}

Therefore, we need to prove a bound on {\mathbb{P}(\omega(G_{V})<k)}, 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)<k]&=&\mathbb{P}[Y=0]\\ &=&\mathbb{P}[Y-\mathbb{E}[Y]=-\mathbb{E}[Y]]\\ &=&\mathbb{P}[Y_N-Y_0=-\mathbb{E}[Y]]\\ \end{array}

Therefore, applying the Azuma-Hoeffding inequality, we get

\displaystyle \mathbb{P}[\omega(G)<k]\le e^{-\frac{(\mathbb{E}[Y])^2}{2N}}\,. \ \ \ \ \ (2)

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<k)&\le &{n \choose m} \exp\Big(-\frac{m^{2(2-\varepsilon)a+o(1)}}{n(n-1)}\Big)\\ &\le& \exp\Big(m^{1+o(1)}(\ln 2)-\frac{m^{2(2-\varepsilon)a+o(1)}}{n(n-1)}\Big)=o(1)\,. \end{array}

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
Categories: Announcement | Comments Off

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<j}} 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.

lecture1-complexity

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<j} \eta_{ij}}.  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.

lecture1-chromatic

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

Newer posts →

css.php