{'fraction_non_alphanumeric': 0.05928468608127561, 'fraction_numerical': 0.01822611006533053, 'mean_word_length': 3.8780382413308847, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Rare event asymptotics for exploration processes for random graphs

Much of the work in the study of large deviations for random graph models is focused on the dense regime where the theory of graphons has emerged as a principal tool. In contrast there is much less known about large deviations for random graph models in the sparse regime. The aim of this paper is to develop an approach for the study of large deviation problems in this regime by establishing Large Deviation Principles (LDP) on suitable path spaces for certain exploration processes of the associated random graph sequence. Our work focuses on the study of one particular class of random graph models, namely the configuration model; however the general approach of using exploration processes for studying large deviation properties of sparse random graph models has broader applicability. The goal is to study asymptotics of probabilities of non-typical behavior in the large network limit. The first key step for this is to establish a LDP for an exploration process associated with the configuration model. A suitable exploration process here turns out to be an infinite dimensional Markov process with transition probability rates that diminish to zero in certain parts of the state space. Large deviation properties of such Markovian models is challenging due to poor regularity behavior of the associated local rate functions. Next, using the rate function in the LDP for the exploration process we formulate a calculus of variations problem associated with the asymptotics of component degree distributions. The second key ingredient in our study is a careful analysis of the infinite dimensional Euler-Lagrange equations associated with this calculus of variations problem. Exact solutions are identified which then provide explicit formulas for decay rates of probabilities of non-typical component degree distributions and related quantities. Please see the paper for the complete abstract.


Introduction
Large deviations for random graph models has been a topic of significant recent research activity (see, e.g., [3, 13-16, 28, 29]). Much of the work in this area is focused on the class of dense random graph models (number of edges in the graph scale like n 2 , where n is the number of vertices). In this regime, the theory of graphons obtained under dense graph limits [4,5,16,24] has emerged as a key tool in the study of large deviation asymptotics. In contrast to the above papers, the focus in the current work is on a sparse random graph setting where the average degree of a typical vertex is O(1) so that the number of edges in the graph are O(n) as n → ∞. Much less is known on rare event asymptotics for random graph models in this regime. The goal of this work is to develop an approach for the study of large deviation problems in the sparse regime by establishing large deviation principles for a class of stochastic dynamical systems, known as the exploration processes, that play a central role in the study of sparse random graphs. Our work focuses on one particular class of random graph models, namely the configuration model; however similar techniques are expected to be useful for other sparse random graph models as well where tractable dynamic constructions via exploration processes are available.
The configuration model refers to a sequence of random graphs with number of vertices approaching infinity and the degree distribution converging to a pre-specified probability distribution p = {p k } k∈N on the set of non-negative integers [1,2,25]. This random graph model is a basic object in probabilistic combinatorics (cf. [30] and references therein) and is one of the standard workhorses in the study of networks in areas such as epidemiology [27] and community detection [18,23]. An important problem for such random graph models is to estimate probabilities of non-typical structural behaviors, particularly when the system size is large. Examples of such behavior include, graph components that are larger or smaller than that predicted by the law of large number analysis or degree distributions within components that deviate significantly from the overall degree distribution. In particular, we are interested in probabilities of events E n,ε (q) associated with the configuration model random graph G n on n vertices, described as E n,ε (q) = {there exists a component in G n with m k degree k vertices, where m k ∈ [n(q k − ε), n(q k + ε)], k ∈ N}, (1.1) and where q = (q k ) k∈N is such that 0 ≤ p k ≤ q k for every k. One of our main results (see Theorem 2.6) shows that, under conditions, for large n and small ε P {E n,ε (q)} ≈ exp {−n [H(q) + H(p − q) − H(p)]} , (1.2) where for a nonnegative sequence r = (r k ) k∈N , This result in particular gives asymptotics for probabilities of observing a component of a given size (see Remark 2.12) and explicit formulas for rates of decay of probabilities of observing a D-regular component of a given size in G n (see Corollaries 2.8 and 2.11); see also Conjectures 2.9 and 2.10 on large deviation asymptotics for the size of the largest component in a D-regular graph. The starting point of our analysis is a dynamical construction of the configuration model given through a discrete time infinite dimensional Markov chain referred to as the exploration process (cf. [20,26]). As the name suggests, the exploration process is constructed by first appropriately selecting a vertex in the graph and then exploring the neighborhood of the chosen vertex until the component of that vertex is exhausted. After this one moves on to another 'unexplored' vertex resulting in successive exploration of components of the random graph until the entire graph has been explored. The stochastic process corresponding to one particular coordinate of this infinite dimensional Markov chain encodes the number of edges in any given component through the length of its excursions away from zero. The remaining coordinates of this Markov chain can be used to read off the number of vertices of a given degree in any given component of the random graph. See Section 2.3 for a precise description of the state space of this Markov chain. The exploration process can be viewed as a small noise stochastic dynamical system in which the transition steps are of size O(1/n) with n denoting the number of vertices in the random graph. A key ingredient in the proof of Theorem 2.6, is a Large Deviation Principle (LDP) for an infinite dimensional jump-Markov process that can be viewed as a continuous time analogue of the exploration process. This result, given in Theorem 2.14, is our second main result. As other applications of this theorem, we recover a well known result on the asymptotics of the largest component in the configuration model due to Molloy and Reed [26] and Janson and Luczak [20], and also present a result (whose proof is omitted) on asymptotics of scaled number of components in a configuration model (see Remark 2.15). The rate function in the LDP given in Theorem 2.14 can be used to formulate a calculus of variations problem associated with the event E n,ε (q) described in (1.1). This problem is at the heart of our analysis and by studying the corresponding infinite dimensional system of coupled Euler-Lagrange equations we construct an explicit minimizer in this optimization problem (see Lemma 7.6). The cost associated with the minimizer is the exponent on the right side of (1.2) and provides the exact expression for the decay rate for the probability of interest.

Proof techniques and overview of contributions
In addition to the study of the asymptotics of the configuration model, one of the main motivations for working on these sets of problems was the development of new techniques for handling large deviations for processes with "degeneracies." We will give an overview of these contributions in this section.
The exploration process associated with the n-th random graph (with n vertices) in the configuration model is described as an R ∞ -valued 'small noise' Markov chain {X n (j)} j∈N0 . Under our assumptions, there exists a N ∈ N such that for all j ≥ nN , X n (j) = 0 for all n ∈ N. In order to study large deviations for such a sequence, one usually considers a sequence of continuous times processes, or equivalently C([0, N ] : R ∞ )-valued random variables, obtained by a linear interpolation of {X n (j)} j∈N0 over intervals of length 1/n. A large deviations analysis of such a sequence in the current setting is challenging due to 'diminishing rates' feature of the transition kernel (see (2.5)) which in turn leads to poor regularity of the associated local rate function. By diminishing rates we mean the property that probabilities of certain transitions, although non-zero, can get arbitrarily close to 0 as the system becomes large. In the model we consider, the system will go through phases where some state transitions have very low probabilities, that are separated by phases of 'regular behavior,' many times. In terms of the underlying random graphs the first type of phase corresponds to time periods in the dynamic construction that are close to the completion of exploration of one component and beginning of exploration of a new component. The poor regularity of the local rate function makes standard approximations of the near optimal trajectory that are used in proofs of large deviation principles for such small noise systems hard to implement. In order to overcome these difficulties we instead consider a different continuous time process associated with the exploration of the configuration model. This continuous time process is obtained by introducing i.i.d. exponential random times before each step in the edge exploration Markov chain. A precise description of this process is given in terms of stochastic differential equations (SDE) driven by a countable collection of Poisson random measures (PRM), where different PRMs are used to describe the different types of transitions (see Section 2.4). Although the coefficients in this SDE are discontinuous functions, their dependence on the state variable is much more tractable than the state dependence in the transition kernel of the discrete time model.
Large deviations for small noise SDE driven by Brownian motions have been studied extensively both in finite and infinite dimensions. An approach based on certain variational representations for moments of nonnegative functionals of Brownian motions and weak convergence methods [6,8] has been quite effective in studying a broad range of such systems (cf. references in [11]). A similar variational representation for functionals of a Poisson random measure has been obtained in [11]. There have been several recent papers that have used this representation for studying large deviation problems (see, e.g., [7,10,12]). This representation is the starting point of the analysis in the current work as well, however the application of the representation to the setting considered here leads to new challenges. One key challenge that arises in the proof of the large deviations lower bound can be described as follows. The proof of the lower bound based on variational representations and weak convergence methods, for systems driven by Brownian motions, requires establishing unique solvability of controlled deterministic equations of the form dx(t) = b(x(t))dt + σ(x(t))u(t)dt, x(0) = x 0 , (1.4) where u ∈ L 2 ([0, T ] : R d ) (space of square integrable functions from [0, T ] to R d ) is a given control. It turns out that the conditions that are typically introduced for the well-posedness of the original small noise stochastic dynamical system of interest (e.g. Lipschitz properties of the coefficients b and σ) are enough to give the wellposedness of (1.4). For example when the coefficients are Lipschitz, one can use a standard argument based on Gronwall's lemma and an application of the Cauchy-Schwarz inequality to establish the desired uniqueness property. In contrast, when studying systems driven by a PRM one instead needs to establish wellposedness of controlled equations of the form 1 [0,g(x(s))] (y)ϕ(s, y)ds m(dy), 0 ≤ t ≤ T, (1.5) where S is a locally compact metric space, m a locally finite measure on S, g : R → R + is a measurable map and the control ϕ is a nonnegative measurable map on [0, T ] × S which satisfies the integrability property where ℓ(x) = x log x − x + 1. If ϕ were uniformly bounded and g sufficiently regular (e.g., Lipschitz) uniqueness follows once more by a standard Gronwall argument. However, in general if g is not Lipschitz or ϕ is not bounded (both situations arise in the problem considered here, see e.g. (2.14)-(2.15)) the problem of uniqueness becomes a challenging obstacle. One of the novel contributions of this work is to obtain uniqueness results for equations of the form (1.5) when certain structural properties are satisfied. The setting we need to consider is more complex than the one described above in that there is an infinite collection of coupled equations (one of which corresponds to the Skorokhod problem for one dimensional reflected trajectories) that describe the controlled system. However the basic difficulties can already be seen for the simpler setting in (1.5). Although for a general ϕ the unique solvability of equations of the form (1.5) may indeed be intractable, the main idea in our approach is to argue that one can perturb the original ϕ slightly so that the solution x(·) stays the same and moreover this x(·) is the unique solution of the corresponding equation with the perturbed ϕ. Furthermore the cost difference between the original and perturbed ϕ is appropriately small. The uniqueness result given in Lemma 5.1 is a key ingredient in the proof of the lower bound given in Section 5. The proof of the upper bound, via the weak convergence based approach to large deviations relies on establishing suitable tightness and limit characterization results for certain controlled versions of the original small noise system. This proof is given in Section 4. The rate function in the LDP for the exploration process in Theorem 2.14 is given as a variational formula on an infinite dimensional path space (see (2.12)). Getting useful information from such an abstract formula in general seems hopeless, however, as we show in this work, for the event considered in (1.1), the variational formula can be used to extract much more explicit information. We begin by observing (see (7.1)) that the event E n,ε (q) of interest can be written explicitly in terms of the exploration process. Using this and the LDP in Theorem 2.14 one can provide an upper bound for the probability of the event in terms of a quantity I 2 0,τ ((0, p), (0, p − q)) which can be interpreted (see Section 7 for a precise definition) as the minimal cost for certain controlled analogues of the exploration process to move from the state (0, p) to (0, p−q) in τ units of time, where τ = 1 2 ∞ k=1 kq k (see Lemmas 8.2 and 8.3). We then show that this deterministic control problem, which can be reformulated as a calculus of variations problem, admits an explicit solution. This solution is given in Construction 1 and its optimality is studied in Lemma 7.6. Using this optimality property, the complementary lower bound for the probability of interest is given in Lemma 8.4. Lemmas 7.6 and 8.4 form the technical heart of the proof of Theorem 2.6 and rely on a detailed and careful analysis of the infinite dimensional Euler-Lagrange equations associated with the calculus of variations problem.

Organization of the paper
The paper is organized as follows. In Section 2 we introduce the configuration model, our main assumptions, and our first main result, Theorem 2.6, on asymptotics of probabilities of E n,ε (q). We record some consequences of these results for D-regular graphs and subgraphs in Corollaries 2.8 and 2.11. Remark 2.12 discusses another application of this result to the study of asymptotics of probabilities of components of a given size. In Section 2.3 we review the edge-exploration algorithm (EEA) from [20,26] that gives a dynamical construction of the configuration model. For reasons discussed previously, the large deviation analysis of the discrete time EEA presents several technical obstacles and thus in Section 2.4 we introduce a closely related continuous time jump-Markov process (X n , Y n ) with values in (R × R ∞ + ) × R which is mathematically more tractable. Sections 2.5 and 2.6 present our second main result, Theorem 2.14, that gives a large deviation principle for the sequence (X n , Y n ) n∈N in a suitable infinite dimensional path space. In Section 2.6 we also note two side consequences of Theorem 2.14. The first, given in Section 2.6.1 is a law of large numbers (LLN) result that recovers well known results of Janson and Luczak (2009) on the asymptotics of the largest component in the configuration model. The second, discussed in Remark 2.15, gives a LDP for the scaled number of components in G n as n → ∞.
Section 3 presents the variational representation from [11] for functionals of PRM that is the starting point of our proofs. Some tightness and characterization results that are used both in the upper and lower bound proofs are also given in this section. Next, Section 4 gives the proof of the large deviation upper bound whereas the proof of the lower bound is given in Section 5. Finally, Section 6 establishes the compactness of level sets of the function I T defined in Section 2.6, thus proving that I T is a rate function. Together, results of Sections 4, 5 and 6 complete the proof of Theorem 2.14.
We next turn to the proof of Theorem 2.6 which is given in Sections 7-9. First in Section 7 we introduce a calculus of variations problem that is central to the proof of Theorem 2.6. We also introduce (see Construction 1) a candidate minimizer in this optimization problem and present several technical results (Lemmas 7.1-7.6) that are needed for the proof of the optimality property of the candidate minimizer. Using results of Section 7 the proof of Theorem 2.6 is completed in Section 8. Finally, Section 9 contains the proofs of technical lemmas from Section 7 whereas Section 10 presents the proof of the LLN results from Section 2.6.1.

Notation
The following notation will be used. For a Polish space S, denote the corresponding Borel σ-field by B(S). Denote by P(S) (resp. M(S)) the space of probability measures (resp. finite measures) on S, equipped with the topology of weak convergence. Denote by C b (S) (resp. M b (S)) the space of real bounded and continuous functions (resp. bounded and measurable functions). For f : For a Polish space S and T > 0, denote by C([0, T ] : S) (resp. D([0, T ] : S)) the space of continuous functions (resp. right continuous functions with left limits) from [0, T ] to S, endowed with the uniform topology (resp. Skorokhod topology). We say a collection {X n } of S-valued random variables is tight if the distributions of X n form a relatively compact collection in P(S). A sequence of D([0, T ] : S)-valued random variables is said to be C-tight if it is tight in D([0, T ] : S) and every weak limit point takes values in C([0, T ] : S) a.s. We use the symbol '⇒' to denote convergence in distribution.
We denote by R ∞ the space of all real sequences which is identified with the countable product of copies of R. This space is equipped with the usual product topology. For x = (x k ) k∈N , y = (y k ) k∈N , we . Let x + . = max{x, 0} for x ∈ R. Denote by R + the set of all non-negative real numbers. Let N 0 . = N ∪ {0}. Cardinality of a set A is denoted by |A|. For n ∈ N, let [n] . = {1, 2, . . . , n}. We use the following conventions: 0 log 0 = 0, 0 log(x/0) = 0 for x ≥ 0, and x log(x/0) = ∞ for x > 0.

Assumptions and Results
Fix n ∈ N. We start by describing the construction of the configuration model of random graphs with vertex set [n]. Detailed description and further references for the configuration model can be found in [30,Chapter 7].

The configuration model and assumptions
be a degree sequence, namely a sequence of non-negative integers such that i . We will usually suppress the dependence of d (n) i and m (n) on n in the notation. Using the sequence {d i } we construct a random graph on n labelled vertices [n] as follows: (i) Associate with each vertex i ∈ [n] d i half-edges. (ii) Perform a uniform random matching on the 2m half-edges to form m edges so that every edge is composed of two half-edges. This procedure creates a random multigraph G([n], d(n)) with m edges, allowing for multiple edges between two vertices and self-loops, and is called the configuration model with degree sequence d(n). Since we are concerned with connectivity properties of the resulting graph, vertices with degree zero play no role in our analysis, and therefore we assume that d i > 0 for all i ∈ [n], n ≥ 1. We make the following additional assumptions. k /n → p k as n → ∞, for all k ∈ N. We will also usually suppress the dependence of n (n) k on n in the notation. We make the following assumption on moments of the degree distribution.
Assumption 2.2. There exists some ε p ∈ (0, ∞) such that sup n∈N ∞ k=1 n k n k 1+εp < ∞. The above two assumptions will be made throughout this work.

Large Deviation Asymptotics for Component Degree Distributions
We will say that a component of G([n], d(n)) has degree configuration {n k } if the component hasn k vertices with degree k, for k ∈ N. Given 0 ≤ q = (q k , k ∈ N) ≤ p, we are interested in the asymptotic exponential rate of decay of the probability of the event E n,ε (q) introduced in (1.1) that corresponds to the existence of a component in G([n], d(n)) with degree configuration {n k } satisfying (q k − ε)n ≤n k ≤ (q k + ε)n, k ∈ N, namely, we want to characterize lim ε→0 lim n→∞ to exist a component with degree configuration {nq k } we must have ∞ k=1 kq k ≥ 2 ∞ k=1 q k − 1 n . We will in fact assume a slightly stronger condition: This condition says that there are strictly more edges than vertices in the component. Define β .
Remark 2.5. We note that for every 0 ≤ q = (q k , k ∈ N) ≤ p, K(q) and H(q) are finite. Indeed, the finiteness of K(q) is immediate from Assumption 2.2. To see the finiteness of H(q), note that on the one hand where the first inequality follows from non-negativity of relative entropy and putting mass 1 − ∞ k=1 q k on k = 0, and the last inequality once more uses Assumption 2.2.
The following result gives asymptotics of the event E n,ε (q). The proof of the theorem, which is based on Theorem 2.14, is given in Section 8.
Theorem 2.6. Suppose 0 ≤ q ≤ p and that (2.1) is satisfied. Then (i) (Upper bound) when p 1 = 0, we have β(q) = 0, K(q) = 0 and lim sup ε→0 lim sup Remark 2.7. The proof of Theorem 2.6 relies on a large deviation principle for a certain exploration process (see Section 2.4) that is given in Theorem 2.14. The latter result does not require the condition p 1 = 0. Also note that the lower bound in Theorem 2.6 does not require the condition p 1 = 0 either. One can also give an upper bound (without requiring p 1 = 0) in terms of a variational formula given by the right side of (8.4). When p 1 = 0, this variational expression can be simplified and is seen to be equal to −Ĩ 1 (q). This is shown in Lemma 8.3 whose proof crucially relies on the property p 1 = 0.
Whether the two expressions are equal in general when p 1 = 0 remains an open problem.
As an immediate corollary of Theorem 2.6 we have the following result for D-regular graphs, i.e., graphs such that each vertex is of degree D. In the following lim ⋆ represents either lim sup or lim inf.
Corollary 2.8. (D-regular graphs) Suppose that there exists some D ∈ N with D ≥ 3, such that p k = 0, n k = 0 for k = D and p D = 1, n D = n. Fix q D ∈ (0, 1] and denote by E n,ε D (q) the event that there is a component of size Proof. Let q k = 0 for k ∈ N \ {D} and let q = {q k , k ∈ N}. Then since p 1 = 0, we have β(q) = 0 and K(q) = 0. Using (2.3) we havẽ The result then follows from Theorem 2.6.
We note that the expression (2.4) has the same form when q D is replaced by 1 − q D . This suggests that the most likely way of having a component of size around nq D in D-regular graphs is to let almost all of the remaining n(1−q D ) vertices be in one component. Indeed, conditioning on having a component of size around nq D , the remaining vertices can be viewed as a smaller configuration model of D-regular graphs with about n(1 − q D ) vertices. It then follows from the well known results for the asymptotics of the largest component in the configuration model [20,26] (and Theorem 2.18) that these remaining vertices are in one component with high probability.
Based on these observations we make the following conjecture.
We also note that for each fixed a ∈ [0, 1], the function [0, a] ∋ x → x log x + (a − x) log(a − x) ∈ (−∞, 0] is maximized at x = 0 and x = a. This suggests that, the most likely way for the largest component to be of certain size, is to let as many of the remaining components as possible have such a size. Based on this we make the following conjecture on the large deviation behavior of the largest component size for D-regular graphs. The following result gives bounds on probabilities of observing a D-regular subgraph in a configuration model with a general degree sequence (p k ).
Corollary 2.11. Suppose that Assumptions 2.1 and 2.2 hold. Also suppose that Denote by E n,ε (q) the event that the graph has a component that is D-regular and has size N D ∈ [n(q D − ε), n(q D + ε)]. Then Proof. Let q k = 0 for k ∈ N \ {D} and let q = (q k , k ∈ N). As before, since q 1 = 0, we have β(q) = 0 and K(q) = 0. Using (2.3) we havẽ The result then follows from Theorem 2.6.
Remark 2.12. Theorem 2.6 can be used to extract other asymptotic results. We give below one example without proof. Suppose that Assumptions 2.1 and 2.2 hold. Also suppose that p 1 = p 2 = 0. Let r ∈ (0, 1] and denote by E n,ε r the event that the graph has a component that has size N r ∈ [n(r − ε), n(r + ε)]. Then The proof of Theorem 2.6 is given in Section 8.

Edge-exploration algorithm (EEA)
One can construct G([n], d(n)) whilst simultaneously exploring its component structure [20,26], which we now describe. This algorithm traverses the graph by exploring all its edges, unlike typical graph exploration algorithms, which sequentially explore vertices. At each stage of the algorithm, every vertex in [n] is in one of two possible states, sleeping or awake, while each half-edge is in one of three states: sleeping (unexplored), active or dead (removed). Write A V (j), S V (j) for the set of active and sleeping vertices at step j and similarly let S E (j), A E (j), D E (j) be the set of sleeping, active and dead halfedges at step j. We call a half-edge "living" if it is either sleeping or active. Initialize by setting all vertices and half-edges to be in the sleeping state. For step j ≥ 0, write A(j) .
= |A E (j)| for the number of active half-edges and V k (j) for the number of sleeping vertices for the corresponding vector in R ∞ + . At step j = 0, all vertices and half-edges are asleep hence A(0) = 0 and V k (0) = n k for k ≥ 1. The exploration process proceeds as follows: (1) If the number of active half-edges and sleeping vertices is zero, i.e. A(j) = 0 and V (j) = 0, all vertices and half-edges have been explored and we terminate the algorithm.
(2) If A(j) = 0 and V (j) = 0, so there exist sleeping vertices, pick one such vertex with probability proportional to its degree (alternatively pick a sleeping half-edge uniformly at random) and mark the vertex as awake and all its half-edges as active. Thus the transition (A(j), V (j)) to (A(j + 1), V (j + 1)) at step j + 1 takes the form where e k is the k-th unit vector.
(3) If A(j) > 0, pick an active half-edge uniformly at random, pair it with another uniformly chosen living half-edge (either active or sleeping), say e * , merge both half-edges to form a full edge and kill both half-edges. If e * was sleeping when picked, wake the vertex corresponding to the half-edge e * , and mark all its other half-edges active. Thus in this case the transition takes the form The statements in (2) and (3) can be combined as follows: If A(j) = 0 or V (j) = 0, then the transition (A(j), V (j)) to (A(j + 1), V (j + 1)) takes the form (2.5) The random graph G([n], d(n)) formed at the termination of the above algorithm has the same distribution as the configuration model with degree sequence d(n) [20,25].
We note that for j > 0 Note that at each step in the EEA, either a new vertex is woken up or two half-edges are killed. Since there are a total of n vertices and 2m half-edges, we have from Assumptions 2.1 and 2.2 that the algorithm terminates in at most m + n ≤ nL steps where L .
We define A(j) ≡ 0 and V (j) ≡ 0 for all j ≥ j 0 where j 0 is the step at which the algorithm terminates.

An equivalent continuous time exploration process
A natural way to study large deviation properties of the configuration model is through the discrete time sequence {A(j), V (j)} j∈N0 in EEA which can be viewed as a discrete time "small noise" Markov process. In order to study large deviations for such a sequence, a standard approach is to consider the sequence of C([0, L] : R ∞ )-valued random variables obtained by a linear interpolation of {A(j), V (j)} j∈N0 over intervals of length 1/n. As was noted in the Introduction, the 'diminishing rates' feature of the transition kernel (2.5) makes the large deviations analysis of this sequence challenging. Thus we introduce below a different continuous time process associated with the exploration of the configuration model. We begin with some notation that will be needed to formulate the continuous time model. For a locally compact Polish space S, let M F C (S) be the space of all measures ν on (S, B(S)) such that ν(K) < ∞ for every compact K ⊂ S. We equip M F C (S) with the usual vague topology. This topology can be metrized such that M F C (S) is a Polish space (see [11] for one convenient metric).
We think of N ϕ k as a controlled random measure, where ϕ is the control process that produces a thinning of the point process N k in a random but non-anticipative manner to produce a desired intensity. We Note that k∈N0 r k (x) = 1 whenever r(x) > 0. Recall that e k is the k-th unit vector in R ∞ , k ∈ N 0 . Define the state process X n (t) = (X n 0 (t), X n 1 (t), X n 2 (t), . . . ) with values in R × R ∞ + as the solution to the following SDE: where X n (0) . = 1 n (−1, n 1 , n 2 , . . . ). The existence and uniqueness of solutions to this SDE follows from Assumption 2.2. It is not difficult to see that 1 . . ) in the discrete time EEA can be viewed as the embedded Markov chain associated with X n . In defining the state process, one could replace X n 0 (0) with the asymptotically equivalent process X n 0 (0) + 1/n which starts from 0 and is more directly comparable with the sequence A(j)/n. However some of the expressions are simplified (see, e.g., the formulas for rates in (2.6) and the transition probabilities in (2.5)) when describing the state in terms of X n 0 (0) instead of X n 0 (0) + 1/n. We now rewrite the evolution of X n as follows: Here the first two integrands do not depend on the sign of X n 0 and are interpreted as the main contribution to the evolution. The last sum is a 'reflection' term in the e 0 direction and makes a contribution of 2 n e 0 only when X n Using these we can write Here η n is viewed as the regulator function which ensures that X n 0 (t) ≥ − 1 n . Note that for k ∈ N, X n k (t) is non-increasing and non-negative. Also, from (2.7) we see that r(X n (t)) is non-increasing.

Rate Function
The main result of this work gives a large deviation principle for {(X n , Y n )} n∈N in the path space D ∞ × D. In this section we define the associated rate function I T . Including the process Y n in the LDP is convenient for obtaining large deviation results, for the degree distribution in giant components, of the form given in Section 10.
Recall the probability distribution p Let C T be the subset of C ∞ × C, consisting of those functions (ζ, ψ) such that (a) ψ(0) = 0, and ψ is absolutely continuous on [0, T ].
(a) From Assumptions 2.1 and 2.2 it follows that the following uniform integrability holds: This in particular says that r(ζ(·)) ∈ C, where r(·) is defined in (2.6).
This follows since ζ k is non-increasing and non-negative for every k.
Thus whenever such a t * exists, ζ(t) = 0 after the time instant

LDP and LLN for the Exploration Process
The following LDP is one of our main results and is key to the proof of Theorem 2.6.
Theorem 2.14. The function I T in (2.12) is a rate function on D ∞ × D and the sequence Outline of the proof: Due to the equivalence between a large deviation principle and a Laplace principle, it suffices to show the following three statements (cf. [17, Section 1.2] or [9, Section 1.2]).
(1) Laplace principle upper bound: Statements (1), (2) and (3) will be shown in Sections 4, 5 and 6, respectively. Remark 2.15. As noted above, the LDP in Theorem 2.14 is a key to the proof of Theorem 2.6. In the next subsection we will show how this LDP can be used to easily give a LLN result. The LDP can be used to establish other asymptotic results as well. We give one such example without proof below. Denote by C n the number of components in G([n], d(n)). Then η n defined in (2.9) can be used to represent C n n . Note that whenever the EEA starts to explore a new component, X n 0 will jump from − 1 n and as a result, η n will increase by 2 n . Therefore Observe from (2.10) that η n = X n 0 − Y n , and that for large deviation asymptotics one can assume that the EEA terminates by time N . Lemma 8.1 and its proof for precise details). Using this fact, Theorem 2.14, and the contraction principle one can establish that C n n satisfies a large deviation principle in R + with rate functionÎ defined bŷ The rate functionÎ(x) has the following alternative representation. dt.

Law of large number limits
The LDP in Theorem 2.14 can be used to identify the LLN limit (ζ, ψ) of the exploration process (X n , Y n ), which corresponds to the unique pair satisfying I T (ζ, ψ) = 0. In particular we recover well known results for the asymptotics of the largest component in the configuration model [20,26]. We assume the following strengthened version of Assumption 2.2.
Then f s (t) is strictly decreasing until it hits zero. Note that in particular, The following theorem together with Proposition 2.19 characterizes the unique (ζ, ψ) ∈ C T that minimizes the rate function I T (ζ, ψ). Letting .
The following proposition says that there is a unique (ζ, ψ) satisfying I T (ζ, ψ) = 0, so that this pair is the law of large numbers limit.

Representation and Weak Convergence of Controlled Processes
We will use the following useful representation formula proved in [11]. For the second equality in the theorem see the proof of Theorem 2.4 in [7]. The representation in the cited papers is given in terms of a single Poisson random measure with points in a locally compact Polish space. However for the current work it is convenient to formulate the representation in terms of a countable sequence of independent Recall the function ℓ defined in (2.13).
There is a bar in the notationX n ,Ȳ n (andν n defined in (3.12) below) to indicate that these are 'controlled' processes, given in terms of the control sequence ϕ n . = (ϕ n k ) k∈N0 . We will occasionally suppress the dependence on ϕ n in the notation and will make this dependence explicit if there are multiple controls (e.g. as in Section 4) In the proof of both the upper and lower bound we will show it is sufficient to consider a sequence {ϕ n k ∈Ā + , k ∈ N 0 } that satisfies the following uniform bound for some M 0 < ∞: In the rest of this section we study tightness and convergence properties of controlled processes (X n ,Ȳ n ) that are driven by controls {ϕ n k } that satisfy the above a.s. bound.
Here the last line follows on observing that ) ≤ m 1 and 0 ≤X n k (t) ≤ n k n . Also note that both r(X n (·)) andX n k (·) for k ∈ N are non-increasing.
The following lemma summarizes some elementary properties of ℓ. For part (a) we refer to [10, Lemma 3.1], and part (b) is an easy calculation that is omitted.
The next lemma gives some uniform integrability properties for the control sequence ϕ n .
Proof. From (3.9) and (3.8) it follows that Recalling The result follows.
The following lemma proves some key tightness properties. WriteB n .
Proof. We will argue the tightness of {B n }, and {η n } in D ∞ , D, D ∞ , and D respectively. This will complete the proof. We now show that {(Ȳ n (t),B n (t),η n (t)))} is tight for each t. From (3.6), (3.9) and (3.10), where the last line uses the definition ofŪ 1 in (3.11). From Lemma 3.2(b) and (3.5), we have We now consider fluctuations of (Ȳ n ,B n ,η n ). Recall the filtration {F t } 0≤t≤T . For δ ∈ [0, T ], let T δ be the collection of all [0, T − δ]-valued stopping times τ . Note that for τ ∈ T δ , Thus in order to argue tightness of {(Ȳ n ,B n ,η n )}, by the Aldous-Kurtz tightness criterion (cf. [ From (3.9) and (3.10) it follows that for every K ∈ N and M ∈ (0, ∞), Using Lemma 3.2(a) and (3.5), we can bound the last display by Taking M → ∞ and then K → ∞, we have from Lemmas 3.2(a) and 3.3 that (3.13) holds. Finally C-tightness is immediate from the following a.s. bounds and Assumption 2.2: for any k ∈ N 0 , K ∈ N and t ∈ (0, T ], This completes the proof. Next we will characterize weak limit points of {(ν n ,X n ,Ȳ n ,B n ,η n )}. For that, we need the following notation. For k ∈ N 0 define the compensated process whereB n k (t) We have the following characterization of the weak limit points. Recall S T (ζ, ψ) defined in (2.14) and (2.15).
(a) This is an immediate consequence of the bound in (3.5) and Lemma A.1 of [7]. (b) The first statement is an immediate consequence of the C-tightness argued in the proof of Lemma 3.4. Then using (3.8), Assumption 2.1 and the fact thatX n k (t) ≥ 0 a.s., we have (3.15). Next, note that by Assumption 2.
(c) By Doob's inequality, as n → ∞ where the second inequality follows from Lemma 3.2(b) and the third inequality follows from (3.5). Therefore as n → ∞B n ⇒ 0. (3.20) By appealing to the Skorokhod representation theorem, we can assume without loss of generality that (ν n ,X n ,Ȳ n ,B n ,η n ,B n ) → (ν,X,Ȳ ,B,η, 0) a.s. on (Ω * , F * , P * ), namely there exists some event Fixω ∈ F . The rest of the argument will be made for such anω which will be suppressed from the notation. From (3.19) we have that as n → ∞ uniformly in t ∈ [0, T ], and r(X(·)) is continuous. Letτ .

Laplace upper bound
In this section we prove the Laplace upper bound (2.17).
From (3.1), for every n ∈ N, we can chooseφ n .

Laplace lower bound
In this section we prove the Laplace lower bound (2.18).
The following lemma, which shows unique solvability of the ODE (2.14) and (2.15) for controls ϕ in a suitable class, is key in the proof.
Step 1: We will prove that Suppose not, namely there exists k ∈ N such that τ k .
It then follows from (2.15) that ζ k (t) =ζ k (t) for all t ≤ τ k + δ k . This contradicts the definition of τ k . Therefore (5.3) must hold.

Compact Sub-level Sets
In this section we prove that the function I T defined in (2.12) is a rate function, namely the set Γ N . = {(ζ, ψ) ∈ D ∞ × D : I T (ζ, ψ) ≤ N } is compact for each fixed N ∈ [0, ∞). Since the proof (as is usual) is very similar to the proof of the Laplace upper bound we will only provide details on steps that are significantly different.
Since we have proved (6.5) for k = 0 and all t < τ , t = τ and t > τ , the proof is complete.
Proof of compact sub-level sets Γ M : Now we are ready to prove that Γ M is compact for each fixed M ∈ [0, ∞). Recall (ζ n , ψ n ) introduced above (6.1) and ν n introduced above Lemma 6.1. From Lemma 6.1 we have pre-compactness of Assume without loss of generality that (ν n , ζ n , ψ n ) converges along the whole sequence to some (ν, ζ, ψ). By Lemma 6.2 (ζ, ψ) ∈ C T and ν = ν ϕ , where for k ∈ N 0 , ν ϕ k is as defined by the right side of (3.12) replacing ϕ n k with ϕ k , and ℓ(ϕ k (s, y)) ds dy ≤ M.
• Finally Proposition 7.7 shows that completing the proof of Theorem 2.6.
Note that for (ζ, ψ) )} the exploration remains in the same component over [t 1 , t 2 ], and on the smaller event {(X n , Y n ) ∈ J 2 t1,t2 (x (1) , x (2) )} the exploration pace matches that for the discretetime exploration process (with time steps of length 1/n), in which at each step 2 half-edges are killed. The main idea in the proof of the theorem is that in characterizing the asymptotics of the probability of interest one can restrict to J 2 0,τ ((0, p), (0, p − q)), which roughly means that one can restrict to trajectories that avoid the boundary and whose evolution matches that of the original discrete time process of interest removing the artificial "continuous time" aspect of the evolution.
Note that β 0 actually does not play a role in the definition of L(x, β) or ν(·|β). Later on (x, β) will be usually replaced by (ζ(t), ζ ′ (t)) for some absolutely continuous path ζ and t ≥ 0.

Moreover, the right hand side is lower semicontinuous in
Recall the functions H and K from (1.3) and (2.2) respectively. We note that withK andH as introduced in the above lemma, for 0 ≤ q ≤q ≤ p H(q) =H(0, q), K(q) =K((0,q), (0,q − q)). (7.17) The next lemma shows that (ζ,ψ) in Construction 1 is a minimizer for the right side of (7.12).

Proof of Theorem 2.6
In this section we will use Theorem 2.14 and results in Section 7 to prove Theorem 2.6. Let 0 ≤ q ≤ p.
Recall the representation of the event E n,ε (q) given in (7.1). Define Note that E n,ε,T (q) ⊂ E n,ε (q) but they are not equal, since the continuous-time EEA may not terminate by time T . Consider the event that the continuous-time EEA terminates before time T , namely the event F n,T defined as Then E n,ε (q) ∩ F n,T ⊂ E n,ε,T (q) ⊂ E n,ε (q). (8. 3) The following lemma guarantees that in order to study the exponential rate of decay of P (E n,ε (q)), it suffices to study that of P (E n,ε,T (q)). ∞ k=1 k n k n ⌋ + 1 < ∞. So since the discrete time EEA is the embedded chain associated with the continuous time EEA (see Section 2.4), X n will have at most nN jumps before arriving at the absorbing state (− 1 n , 0). Since the total jump rate for X n (t) at any instant before getting absorbed is n ∞ k=0 r k (X n (t)) = n, we have where ξ i are i.i.d. exp(n) andξ i are i.i.d. exp (1). Therefore lim sup as T → ∞, where the second equality is from Cramér's theorem and where L 1 (x) . = x − 1 − log x for x ≥ 0 is the Legendre transform of the log-moment generating function ofξ 1 .
Since I T (ζ, ψ) < ∞ only when (ζ, ψ) ∈ C T , we have lim sup It is easy to see that clẼ ε,T (q) ∩ C T =Ẽ ε,T (q) ∩ C T . Thus we have lim sup we haveẼ T (q) = ε>0 Ẽ ε,T (q) ∩ C T . From this, the lower semi-continuity and compactness of level sets of I T (ζ, ψ) (since I T is a rate function; see Theorem 2.14), it follows I T (ζ, ψ).
Next we will prove the lower bound.
Then the lower bound in (7.4) holds.
For the second term in (8.14), if t n 2 ≤ τ , then using (8.7) and (8.11) we have If t n 2 > τ , then t n 2 = τ n and from the definition of G n j and (8.7) we have Combining these three displays with (8.14) gives From this, and (7.1), (8.12), (8.13) we have ω ∈ E n,ε (q). Since δ < δ 0 and n > n 0 is arbitrary, the claim (8.8) holds. For fixed δ < δ 0 and n > n 0 consider the following two probabilities P (A n δ (ζ,ψ)), P ((X n , Y n ) ∈G δ (ζ,ψ)). Write where we only have to sum up to ⌊δn⌋ in the last line when (X n , Y n ) ∈G δ (ζ,ψ) sinceζ 0 (τ ) = 0. Since τ n = τ on {X n 0 (τ ) = − 1 n }, we have From Assumption 2.2 and the fact that r(X n (t)) is non-increasing it follows Hence for odd integer 1 ≤ j ≤ ⌊δn⌋ and δ < C0 2 , where the last inequality follows since the term on the last line includes more fractions that are less than 1 than the one on the previous line. For the first equality we have used the fact that on the event G n j all the active j + 1 half edges (an even number) at time instant τ should merge among themselves (without waking any sleeping vertices) by the time instant τ n , whereas the total number of available half edges (either awake or sleeping) at time instant τ equals nr(X n (τ )) + 1.
Proof of Lemma 7.3.
We claim that we can interchange the integration and summation in the last line. To see this, first note that there exists some M ∈ N such that z k ≤z k ≤ 2z k ≤ 2p Usingl(x) . = x log x − x = log x dx, the last expression equals Here the last term is clearly finite. LettingM .
where the inequality holds since log x is concave and log x ≤ x. Therefore One can easily verify that for 1 ≤ k ≤ M , So the claim holds. Actually we have also shown that t1+τ t1 L(ζ(s),ζ ′ (s)) ds < ∞.

Proof of Lemma 7.6
We begin with a lemma that gives the statement in Lemma 7.6 under a stronger assumption.