Get Complete Project Material File(s) Now! »

## The phase transition and critical behaviour of the component sizes

As we have already mentioned, Gn() undergoes a phase transition in its component sizes depending on its parameters [112, 113, 90]. Indeed, if () 1, then the largest connected component Gn1of Gn() is such that jGn1 j=n p! 0. On the other hand, if () > 1 then jGn1 j=n p!( ), where ( ) is some strictly positive constant. These results also hold for Mn(). To give an idea of why the quantity () is important, imagine performing the depth- rst exploration outlined above, but ignoring any edges which create cycles. Then it is not hard to see that, at each step which is not the start of a component, the degree of the vertex to which the half-edge on the top of the stack connects (as long as it does not connect to something on the stack and thus create a cycle) is a size-biased pick from among the remaining possibilities. So, at least close to the beginning, the exploration process should look approximately like a branching process with ospring distribution given by D 1, where P (D = k) = kk=E[D1].

But then () = E[D 1], and so the critical point for the approximating branching process is indeed () = 1. Our interest is in this precisely critical case, and a signicant part of this paper is devoted to making the heuristic argument just outlined precise.

### Branching processes and their metric space scaling limits

As alluded to above, the components of our critical random graphs behave approximately like critical branching process trees. It will be useful to spend a little time now exploring what happens in the true branching process setting, since what we do later will be analogous. Suppose that we take a sequence of i.i.d. Galton{Watson trees, with ospring distribution represented by some non-negative random variable Y with E[Y ] = 1 and P (Y = 1) < 1. (This entails that each of the trees has nite size almost surely.) We use the standard encoding of this forest in terms of its Lukasiewicz path or depth-rst walk, given by S(0) = 0 and S(k) = Pk i=1(Yi1) for k 1 (see Le Gall [95] or Duquesne and Le Gall [70] for more details). Here, as usual, we explore the vertices of the forest in depth-rst order, and Yi is the number of children of the ith vertex that we visit; these get added to the stack to await processing. The stack-size process is essentially a re ected version of S, given by (1+S(k)min0jk S(j))k0. It is straightforward to see that the individual trees correspond to excursions above the running minimum of (S(k))k0; it is technically easier to work with the depth-rst walk than with the stack-size process, since S it is an unre ected random walk. An even more convenient encoding of the forest is given by the height process, which tracks the generation of the successive vertices listed in depth-rst order. (It is, however, considerably harder to understand its distribution.) In terms of the depth-rst walk, the height process (G(n))n0 is dened by G(0) = 0 .

#### Related work on scaling limits of critical random graphs, universality, and open problems

This paper is a contribution to a now extensive literature on scaling limits of critical random graphs. In this section, we will place our work in context by giving a summary of related results. As mentioned above, the rst critical random graph to be studied from the perspective of scaling limits was the Erd}os-Renyi random graph, in the work of Aldous [13], who considered both component sizes and surpluses. Addario-Berry, Broutin and Goldschmidt [6, 5] built on Aldous’ work in order to prove convergence to the = = 1 Brownian graph, in the sense of an `4 version of the Gromov{Hausdor distance. (It is straightforward to improve this to a convergence in an `4 version of the Gromov{Hausdor{Prokhorov distance, which appears as Theorem 4.1 of Addario-Berry, Broutin, Goldschmidt & Miermont [7].) Several models have been proved to lie in the same universality class as the Erd}os{Renyi random graph, which is roughly characterised by the property that the degree of a uniformly chosen vertex converges to a limit with nite third moment. Already in [13], Aldous had, in fact, also considered another model: a rank-one inhomogeneous random graph in which, for each n 1, we are given a sequence of weights w(n) = (w(n) 1 ;w(n) 2 ; : : : ;w(n) n ) and each pair of vertices fi; jg is connected independently with probability 1exp(q(n)w(n) i w(n) j ), for 1 i; j n. Such graphs may be constructed dynamically by assigning an exponential clock to each potential edge and including the edge when the clock rings. It is straightforward to see that, in consequence, the component sizes then evolve according to the multiplicative coalescent. In his Proposition 4, Aldous gave conditions on sequences (w(n); q(n))n1 for which one gets convergence of the rescaled component weights to the same limit as for the component sizes in the Erd}os{Renyi case. These results were generalised by Bhamidi, van der Hofstad and van Leeuwaarden [40] to give convergence of the rescaled component sizes in the Norros{Reittu model [119] (for which q(n) above is replaced by 1= Pn i=1 w(n) i ) to the sequence (1; 2; : : 🙂 appearing in Theorem 2.2.1 (i), with a general and . The convergence of the component sizes was also treated in a similar setting but with i.i.d. vertex weights by Turova [134].

**Table of contents :**

**1 Introduction **

1.1 Sparse random graphs

1.2 The phase transition

1.3 The Gaussian Free Field

1.4 The mixing time

**2 Scaling limit of a critical conguration model with power-law degrees **

2.1 Introduction

2.1.1 Overview

2.1.2 Our results

2.2 Background

2.2.1 The conguration model

2.2.2 The phase transition and critical behaviour of the component sizes .

2.2.3 Branching processes and their metric space scaling limits

2.2.4 Our method

2.2.5 Related work on scaling limits of critical random graphs, universality, and open problems

2.2.6 Plan of the rest of the paper

2.3 The limit object: the stable graph

2.3.1 An absolute continuity relation for spectrally positive -stable Levy processes

2.3.2 Excursion theory

2.4 Convergence of a discrete forest

2.5 The conguration multigraph

2.5.1 Exploration of the multigraph

2.5.2 Convergence of the depth-rst walk and marks

2.5.3 Back-edges

2.5.4 Components of the nite graph

2.5.5 Marked excursions

2.5.6 Height process

2.5.7 The convergence of the metric structure

2.6 Appendix

2.6.1 A change of measure for spectrally positive Levy processes

2.6.2 Size-biased reordering

2.6.3 Convergence of the measure-change in the Brownian case

2.6.4 Convergence of a single large component for 2 (1; 2)

**3 Gaussian Free Field level-set percolation on regular random graphs **

3.1 Introduction

3.1.1 Overview

3.1.2 Setting

3.1.3 Results

3.1.4 Discussion and open questions

3.1.5 Proof outline

3.1.6 Plan of the rest of the paper

3.1.7 Further denitions

3.2 Basic properties of Gn

3.2.1 Structure and Green function

3.2.2 GFF on Gn

3.3 The Gaussian Free Field on Td

3.3.1 Ch as a branching process

3.3.2 Exponential growth

3.4 Approximate recursive construction of Gn

3.5 Exploration of Gn around a vertex

3.5.1 Successful exploration

3.5.2 Aborted exploration

3.6 Existence of a giant component

3.6.1 Connecting two successful explorations

3.6.2 Average number of connections in Eh Gn

3.7 Uniqueness of the giant component

3.7.1 Lower bound

3.7.2 First phase

3.7.3 Second phase

3.7.4 Third phase

3.7.5 Revealing Gn on the three phases

3.8 Properties of C(n)

3.8.1 The local limit: proof of Theorem 3.1.3

3.8.2 The core and the kernel: proof of (3.4) and (3.5)

3.8.3 The typical distance: proof of (3.7)

3.8.4 The diameter: proof of (3.6)

**4 Cuto for random walks on random lifts **

4.1 Generic cuto for random lifts of weighted graphs

4.1.1 Introduction

4.1.2 Basic properties

4.1.3 Study of the universal cover

4.1.4 Proofs of Proposition 4.1.2 and Theorem 4.1.1

4.1.5 Relaxing the assumptions

4.1.6 Appendix 1: computing h = hTG and s

4.1.7 Appendix 2: is laziness necessary?

4.2 An example with a precise cuto window: the NBRW on non-weighted graphs .

4.2.1 Setting

4.2.2 Results

4.2.3 Proof of Proposition 4.2.2

4.2.4 Proof of Theorem 4.2.3

4.3 Diameter of random lifts

4.3.1 The growth rate of the universal cover

4.3.2 Proof of Theorem 4.3.1

**Bibliography**