On replica symmetry of large deviations in random graphs

Eyal Lubetzky and I just uploaded to the arXiv our new paper “On replica symmetry of large deviations in random graphs.” In this paper we answer the following question of Chatterjee and Varadhan:

Question. Fix {0<p<r<1}. Let {n} be a large integer and let {G} be an instance of the Erdős-Rényi random graph {\mathcal G(n,p)} conditioned on the rare event that {G} has at least as many triangles as the typical {\mathcal G(n,r)}. Does {G} look like a typical {\mathcal G(n,r)}?

Here the Erdős-Rényi random graph {\mathcal G(n,p)} is formed by taking {n} vertices and adding every possible edge independently with probability {p}. Here “look like” means close in cut-distance (but we won’t give a precise definition in this blog post). In this case, saying that {G} is close to {\mathcal G(n,r)} is roughly equivalent to saying that every not-too-small subset of vertices (at least constant fraction in size) of {G} induce a subgraph with edge density close to {r}.

Another way to phrase the question is: what is the reason for {G} having too many triangles? Is it because it has an overwhelming number of edges uniformly distributed, or some fewer edges arranged in a special structure, e.g., a clique.

Via a beautiful new framework by Chatterjee and Varadhan for large deviation principles in {\mathcal G(n,p)}, we give a complete answer to the above question.

The answer, as it turns out, depends on {(p,r)}. See the plot below. For {(p,r)} in the blue region, the answer is yes, and for {(p,r)} in the red region, the answer is no.

Does {G} looks like a {\mathcal G(n,r)}?

The phase transition behavior has already been observed previously by Chatterjee and Varadhan, but the determination of the exact precise phase boundary is new. Borrowing language from statistical physics, the blue region where the conditional random graph is close to {\mathcal G(n,r)} is called the replica symmetric phase, and the red region is called the symmetry breaking phase. Note that in the left part of the plot, as we fix a small value of {p}, the model experiences a double phase transition as {r} increases from {p} to {1} — starting first in the blue phase, then switches to the red phase, and then switches back to the blue phase.

More generally, our result works for any {d}-regular graph in replace of triangles. The boundary curve depends only on {d}, and they are plotted below for the first few values of {d}. In particular, this means that large deviation for triangles and 4-cycles share the same phase boundary. A pretty surprising fact! We also consider the model where we condition on the largest eigenvalue of the graph being too large, and the phase boundary also turns out to be the same as that of triangles.

We also derive similar results for large deviations in the number of linear hypergraphs in a random hypergraph.

The phase boundary for {d}-regular graphs

Exponential random graphs

We also studied the exponential random graph model. This is a widely studied graph model, motivated in part by applications in social networks. The idea is to bias the distribution of the random graph to favor those with, say, more triangles. This model has a similar flavor to the model considered above where we condition on the random graph having lots of triangles.

We consider a random graph {G} on {n} vertices drawn from the distribution

\displaystyle p_\beta(G) \propto \exp\left(\tbinom{n}{2}(\beta_1 t(K_2, G) + \beta_2 t(K_3, G))\right)\,,

where {t(K_2, G)} and {t(K_3, G)} are the edge density and the triangle density of {G}, respectively. When {\beta_2 = 0}, this model coincides with the Erdős-Rényi model {\mathcal G(n,p)} with some {p} depending on {\beta_1}. We only consider the case {\beta_2 > 0}, which represents a positive bias in the triangle count.

As shown by Bhamidi, Bresler and Sly and Chatterjee and Diaconis, when {n} is large, a typical random graph drawn from the distribution has a trivial structure — essentially the same one as an Erdős-Rényi random graph with a suitable edge density. This somewhat disappointing conclusion accounts for some of the practical difficulties with statistical parameter estimation for such models. In our work, we propose a natural generalization that will enable the exponential model to exhibit a nontrivial structure instead of the previously observed Erdős-Rényi behavior.

Here is our generalization. Consider the exponential random graph model which includes an additional exponent {\alpha>0} in the triangle density term:

\displaystyle p_{\alpha,\beta}(G) \propto \exp\left(\tbinom{n}{2}(\beta_1 t(K_2, G) + \beta_2 t(K_3, G)^\alpha)\right) \, .

When {\alpha \geq 2/3}, the generalized model features the Erdős-Rényi behavior, similar to the previously observed case of {\alpha = 1}. However, for {0< \alpha < 2/3}, there exist regions of values of {(\beta_1, \beta_2)} for which a typical random graph drawn from this distribution has symmetry breaking, which was rather unexpected given earlier results. For example, we know that there is symmetry breaking in the shaded regions in the plots below. (The blue curve indicates a discontinuity in the model which we won’t discuss in this blog post.)

Symmetry breaking in the new exponential graph model

Continue reading →

Graph regularity

In this blog post I will give a brief introduction to Szemerédi’s Regularity Lemma, a powerful tool in graph theory. The post is based on a talk I gave earlier today at a graduate student lunch seminar.

Consider the following problem. Suppose you’re given a very large graph. The graph has so many vertices that you won’t be able to access all of them. But nevertheless you want to find out certain things about the graph. These situations come up in real world applications. Perhaps we would like to know something about a social network, e.g., Facebook, but we don’t have the resource to go through every single node, as there are simply too many of them. For the purpose of this blog post though, we won’t talk about applications and instead stick to the mathematics.

Suppose we are interested answering the following question about the very large graph:

Is the graph triangle-free?

Think of the given graph as a black box. We have the following access to the graph: we are allowed to randomly sample some number of vertices and be told of all the edges between these vertices.

Can we achieve the desired goal? Well, if the graph contains, say, only a single triangle, then it’s pretty much a hopeless task, since we are almost certainly never going to find the single needle in this giant haystack through random sampling. So we have to be content with a more modest objective.

Can we distinguish a graph that’s triangle-free from a graph that is {\epsilon}-far from triangle-free?

Being {\epsilon}-far from a property means that we would have to add/delete at least {\epsilon n^2} edges from the graph to make it satisfy that property. Here {n} is the number of vertices in the very large graph. Note that this model puts us in the setting of dense graphs, i.e., graphs with {\Omega(n^2)} edges.

This problem we know how to solve. The algorithm is very straightforward: sample some constant number of vertices, and check to see if you see any triangles.

Algorithm: Sample {C_\epsilon} (some constant depending on {\epsilon}) vertices

  • If a triangle is detected, then output that the graph is not triangle-free.
  • If no triangle is detected, then output that the graph is triangle-free

If the given graph is triangle-free, then clearly we won’t ever detect any triangles, so the algorithm always outputs the correct answer. But what if the given graph is not triangle-free? We said earlier that in this case we’ll assume the graph is {\epsilon}-far from triangle free. We want the algorithm to detect at least one triangle so that it can give the correct. However, the randomized nature of the algorithm means that there will be some probability that the output will be erroneous. We are claiming that this error probability is small.

This claim seems very innocent. Essentially we need to show that if a graph cannot be made triangle-free by deleting a small number of edges, then it must not contain very many triangles. If you haven’t seen this claim before, you might think that it’s something that would follow from some easy deductions, and you might be tempted to work it out yourself. However, be warned that you will almost certainly not succeed. The claim is indeed correct, but it is far from trivial.

Continue reading →

The critical window for the classical Ramsey-Turán problem

[Update: Po-Shen Loh gave a wonderful talk in Banff about our paper. Here is the video.]

Jacob Fox, Po-Shen Loh and I recently uploaded to the arXiv our new paper “The critical window for the classical Ramsey-Turán problem.” This paper revisits the following celebrated Ramsey-Turán result first proved by Szemerédi in 1972.

Theorem 1 (Szemerédi 1972) For every {\epsilon > 0}, there exists a {\delta > 0} such that any graph on {n} vertices containing no 4-clique and no independent set of size greater than {\delta n} has at most {(1/8 + \epsilon)n^2} edges.

Turán’s theorem tells us that if we just want to construct a {K_4}-free graph on {n} vertices with the largest possible number of edges, then we should divide the {n} vertices into three nearly-equal parts and put in all possible edges across parts. This yields roughly {n^2/3} edges. However, this graph contains very large independent sets with {n/3} vertices. So the independent set restriction (which gives the “Ramsey” part of Ramsey-Turán) rules out this construction and forces the optimal graphs to take on a very different structure.

At the time of Szemerédi’s 1972 result, most people believed that a {K_4}-free graph with largest independent set of size {o(n)} has to be much more sparse, perhaps with only {o(n^2)} edges. So it was a surprise when, four years later, Bollobás and Erdős gave a clever geometric construction, based on the isoperimetric inequality for the high dimensional sphere, that showed that the bound given by Szemerédi is essentially optimal.

Theorem 2 (Bollobás and Erdős 1976) There exists a {K_4}-free graph on {n} vertices with largest independent set of size {o(n)} and having {(1/8 - o(1))n^2} edges.

Bollobás and Erdős asked what happens in the critical window, when the number of edges is about {n^2/8}. This problem has received considerable attention (e.g., it was featured in a paper by Erdős from 1990 titled “Some of my favourite unsolved problems”). One of the difficulties here is that Szemerédi’s original proof used the regularity lemma, which is a powerful tool but one that unfortunately gives very poor parameter dependencies. To obtain results for the Ramsey-Turán problem at the desired precision, a regularity-free proof is needed. We give a new proof of the classical Ramsey-Turán result that avoids the use of regularity. This allows us to obtain much better and in fact nearly-optimal dependencies for the classical Ramsey-Turán problem in the critical window near {n^2/8} edges, and solve several longstanding open problems in this area.

Continue reading →

Extremal results for sparse pseudorandom graphs

David Conlon, Jacob Fox and I have just uploaded to the arXiv our paper Extremal results in sparse pseudorandom graphs. The main advance of this paper is a sparse extension of the counting lemma associated to Szemerédi’s regularity lemma, allowing us to extend a wide range of classical extremal and Ramsey results to sparse pseudorandom graphs.

An important trend in modern combinatorics research is in extending classical results to the sparse setting. For instance, Szemerédi’s theorem says that every subset of the integers with positive density contains arbitrarily long arithmetic progressions. The celebrated result of Green and Tao says that the primes also contain arbitrarily long arithmetic progressions. While the primes have zero density in the integers, they may be placed inside a pseudorandom set of “almost primes” with positive relative density. Green and Tao established a transference principle, allowing them to apply Szemerédi’s theorem as a black box to the sparse setting. Our work has a similar theme. We establish a transference principle extending many classical extremal graph theoretic results to sparse pseudorandom graphs.

One of the most powerful tools in extremal graph theory is Szemerédi’s regularity lemma. Roughly speaking, it says that every large graph can be partitioned into a bounded number of roughly equally-sized parts so that the graph is random-like between pairs of parts. With this tool in hand, many important results in extremal graph theory can be proven using a three-step recipe, known as the regularity method:

  1. Starting with any graph {G}, apply Szemerédi’s regularity lemma to obtain a regular partition;
  2. Clean up the graph and create an associated reduced graph. Solve an easier problem in the reduced graph;
  3. Apply the counting lemma. Profit.

The counting lemma is a result that says that the number of embeddings of a fixed graph (e.g., a triangle) into the regular partition is roughly what you would expect if the large graph were actually random. The original version of Szemerédi’s regularity lemma is useful only for dense graphs. Kohayakawa and Rödl later independently developed regularity lemmas for sparse graphs. However, for sparse extensions of the applications, the counting lemma remained a key missing ingredient and an important open problem in the field. Our main advance lies in a counting lemma that complements the sparse regularity lemma.

Continue reading →