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:
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
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!
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 .
- If , then in probability.
- If , then in probability, for some .
- 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.
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!
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.
Let be set of integers that represent colors. A vertex coloring of a graph is an assignment of a color to each vertex . Furthermore a vertex coloring is said to be proper if for all . The chromatic number of a graph is the smallest number 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 .
Theorem [Bollobas, 1988]
The chromatic number of a random graph satisfies
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 of a graph is a set of vertices such that . Independent sets are sometimes called stable sets. Denote by the complement graph of where iff . If is an independent set of , then it is a clique in . The largest independent set in is called independence number of and denoted by .
Proposition For any graph with independence number , clique number and chromatic number the following holds
2. Chromatic, clique and independence numbers
Our goal is to study the chromatic number of a random graph . It actually builds upon the clique number that we studied during last lecture. Indeed, we will use the following observation: if then so does the complement graph of . It implies that the independence number has the same distribution as the clique number . We know from last lecture that . Therefore, it follows from the above proposition that
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 and let be a subset of vertices and observe that induced subgraph restricted to vertices in has distribution .
That is: every vertex subgraph contains an independent set of size .
Consider now the following coloring procedure to produce a proper coloring. Pull out independent sets of size one by one and give each a distinct color. According to the definition of , as long as there are at least vertices, this is possible. If there are less than vertices left, give each a distinct color.
The above algorithm gives one possible way of coloring graph and thus the output number is an upper bound on the chromatic number . Let us now compute this upper bound. By definition of , we have
Therefore, we need to prove a bound on , uniformly in . 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 be a filtered space and let be a random variable on . Assume that the martingale is such that for all ,
Then for any positive integer and any , it holds,
Proof: We assume the following inequality due to Hoeffding. For any random variable such that a.s. and any , it holds
Now, using a Chernoff bound, we get for any ,
where . The above two displays yield that
The second part of the proof follows by applying the same argument to the martingale .
Consider the lexicographic ordering of and let be iid Bernoulli random variables with parameter indicating the presence of an edge in a graph . Define the -algebra . We are going to apply the Azuma-Hoeffding inequality to the (Doob) martingale where is maximal number of edge-disjoint -cliques in .
Note first that a.s., since adding/removing one edge can add/remove at most one edge disjoint -clique. Moreover, this inequality would not hold if we had chosen to be the number cliques of size (not necessarily disjoint). Indeed, adding or removing an edge can create or destroy many overlapping cliques.
It follows that,
It remains to show that is sufficiently large. Note first that , where is is the number of -cliques that do not share an edge with any other -clique of the graph.
4. A strong lower bound on the clique number
Fix positive integers and
and let denote the number of cliques in that do not share an edge with any other -clique of the graph. Then
for all . Here the asymptotic notation notations are as .
Proof: Define (for large enough) for some to be chosen later.
Moreover, note that for large enough,
so that where is the number of cliques in that do not share an edge with any other -clique of the graph . Let .
For any define the indicator:
Moreover for any set , let denote the number of -cliques in , other than itself, that share at least two vertices with . Observe that
We bound as follows
The following bound holds for all ,
Moreover, for , , it holds
To conclude the proof, observe that by Stirling, since ,
Let and observe that
We can therefore apply the previous proposition together with~(2), to get
5. Proof of the main theorem
we get for ,
Thus . Together with~(1), it yields
Which completes the proof of our theorem.
Lecture and scribing by Philippe Rigollet
In this lecture all logs are in base . We will prove the following.
Theorem For the centered and normalized clique number
That is, as , the clique number of the Erdös-Rényi graph is .
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, denotes an Erdös-Rényi graph .
For the first part one has
Thus, choosing , we obtain
for every , where we used that for large .
For the second part it is useful to introduce some notation. Define
In particular, iff . Thus we want to show that for one has . Using the trivial observation that implies , we get
where we have used Markov’s inequality. Note that by linearity of the expectation, . Furthermore, we can write
As are boolean random variables we have and thus
which tends to for (see the first part of the proof and use the inequality ). Thus it remains to show that the following quantity tends to :
First note that, by the independence of the edges, for with we have that and are independent, so that in the numerator of the above quantity one can restrict to with . Now by an elementary reasoning we have (with being an arbitrary subset of vertices)
Clearly one has
which shows that (1) can be rewritten as
Now note that since
Using one obtains that (2) is bounded from above by
As is a convex function and as , one has . Thus for large enough the exponent in the above display is bounded from above by , and for this latter is bounded by . Thus we proved that (2) is bounded from above by
which tends to as tends to infinity, concluding the proof.
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.
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 be a graph, where is the set of vertices and 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 , where . Thus and for each .
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.
Let be a random graph on vertices, such that is a collection of i.i.d. Bernoulli random variables with , . Such a random graph is called Erdös-Rényi graph, and we denote this model by .
The Erdös-Rényi graph is the simplest random graph model: for example, in a group of people, each pair are friends, independently, with probability . 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 as
This definition is really intended for connected graphs, where it is a meaningful quantity.
For an Erdös-Rényi random graph we have
since . 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.
- Fixed edge probability. Fix and let go to infinity. We expect such a graph to be very dense: on average, a fraction of all possible edges is present, and each vertex is connected with other vertices. In this regime the expected complexity of the graph blows up, that is, . 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.
- Low complexity. Take for some and let 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 .
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 is a complete subgraph, that is, a subset such that for every , . If describes friendships, a clique is a group of mutual friends. Intuitively, a rich graph must contain a large clique. The clique number is the cardinality of the largest clique in .
Theorem 1 Let be an Erdös-Rényi graph. Then
On a heuristic level, we see that this result makes sense since
from which we see that 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 is a color assignment to each vertex in such that for each , and have a different color. The chromatic number is the smallest number of colors needed to color . It is clear that the chromatic number of a graph tells us something about the complexity of the graph.
Theorem 2 Let be an Erdös-Rényi graph. Then
So, in the Erdös-Rényi graph the chromatic number grows as , smaller than in a complete graph were the chromatic number is , but much larger than in trees which can be colored with only 2 colors regardless of their size. That the same factor 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 , so each vertex has neighbors on average:
In this case we expect the graph to be much simpler than in the previous regime. If 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 , let be the connected component of that contains .
- If , then .
- If , then and all other components have size .
- If , then and there are several large components.
Moreover, all with are either trees or have one cycle with high probability.
So, decomposes into many disconnected, simple pieces in the subcritical case . In the supercritical case we get emergence of one giant component that is complex, with some remaining disconnected simple pieces. The critical case is the most complicated. In this case there are additional phase transitions near the critical window , 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 .]
How do we prove such a theorem? We will use a dynamical method: start at , then explore 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!
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).
- Alon and Spencer, “The Probabilistic Method“, Wiley.
- Durrett, “Random Graph Dynamics“, Cambridge.
- Nachmias and Peres, “The critical random graph, with martingales“, Israel J. Math. 176 (2010), p. 29-41.
- Aldous, “Brownian excursions, critical random graphs and the multiplicative coalescent“, Ann. Probab. 25 (1997), p. 812-854.
- Grimmett, “Probability on Graphs“, Cambridge.
- van der Hofstad, “Random Graphs and Complex Networks“, lecture notes
- Bollobas, “Random Graphs“, Cambridge.
- Janson, Luczak, Rucinski, “Random Graphs“, Wiley.