Nathanaël Enriquez

Gabriel Faraud

Laurent Ménard

Nathan Noiry

Nathan Noiry Long

Long induced paths in a configuration model

Keywords: Configuration Model, Induced Paths, Depth First Search Algorithm. 2010 Mathematics Subject Classification. 60K35, 82C21, 60J20, 60F10

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In this paper, we are interested in the existence of long induced cycles and long induced paths in random (multi-)graphs. An induced path of length k ≥ 1 in a (multi-)graph G = (V, E) is a sequence v 1 , . . . , v k of distinct vertices of the graph such that, for any 1 ≤ i, j ≤ k, v i and v j are neighbors in the graph G (i.e. {v i , v j } ∈ E) if and only if |i -j| = 1. Similarly, an induced cycle is a cycle of distinct vertices of the graph such that two non-consecutive vertices are not linked by an edge. Induced cycles are often also called holes of the graph. Our main result, Theorem 1, is a lower bound on the length of induced paths and cycles for random graphs constructed by the configuration model in the supercritical sparse regime. This length is linear in the size of the graph.

The configuration model was introduced by Bollobás in 1980 [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF] and can be defined as follows: Let N ≥ 1 be an integer and let d 1 , . . . , d N ∈ Z + be such that d 1 + • • • + d N is even. We interpret d i as a number of half-edges attached to vertex i. Then, the configuration model C ((d i ) 1≤i≤N ) associated to the sequence (d i ) 1≤i≤N is the random multigraph with vertex set {1, . . . , N } obtained by a uniform matching of these half-edges. If d 1 + • • • + d N is odd, we change d N into d N + 1 and do the same construction.

We are going to study sequences of configuration models whose degree sequences d (N ) satisfy classical hypothesis. The first assumption corresponds to the sparsity of the graphs:

• For every N ≥ 1, d (N ) = (d (N ) 1 , . . . , d (N ) N ) ∈ Z N
+ , and there exists π a probability measure on Z + with finite second moment such that

∀k ≥ 0, 1 N N j=1 1 d (N ) j =k -→ N →+∞ π({k}). (A1)
Such graphs are known to exhibit a phase transition for the existence of a unique macroscopic connected component depending on the properties of the limiting distribution π, see [START_REF] Molloy | A critical point for random graphs with a given degree sequence[END_REF][START_REF] Molloy | The size of the giant component of a random graph with a given degree sequence[END_REF][START_REF] Janson | A new approach to the giant component problem[END_REF]. Our second assumption is that our configuration models are supercritical, meaning that they have 1 arXiv:2106.11130v1 [math.PR] 21 Jun 2021 a unique giant component, so that long induced paths and cycles can have linear length. To state this assumption, we need the following notation: for every s ∈ [0, 1] define f π (s) = i≥0 π({i})s i and fπ (s) = f π (s) f π [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF] .

Our second assumption is then:

• The probability measure π is supercritical in the following sense:

f π (1) > 1. (A2)
Denote by ρ π the smallest positive solution in (0, 1] of the fixed point equation

1 -ρ π = fπ (1 -ρ π ) (1)
and write

ξ π = 1 -f π (1 -ρ π ). (2)
Under Assumptions (A1) and (A2), the giant connected component of C (d (N ) ) has size ξ π N + o(N ) with probability tending to 1 as N → ∞.

Finally, we make two additional technical assumptions on the degree sequences (d (N ) ) N :

• The following convergence holds:

lim N →+∞ d (N ) 1 2 + • • • + d (N ) N 2 N = k≥0 k 2 π({k}). (A3)
• There exists γ > 2 such that:

max d (N ) 1 , . . . , d (N ) N ≤ N 1/γ . ( A4
)
We are now ready to state our main result:

Theorem 1. Let π be a probability measure on Z + with generating series f π and (C (d (N ) )) N ≥1 be a configuration model with supercritical asymptotic degree distribution π satifsying assumptions (A1) (A2), (A3) and (A4). Denote by H N be the length of the longest induced cycle or induced path in C (d (N ) ). Let α c be the smallest positive solution of the equation

f π f -1 π (1 -α) f π (1) = 1.
For every α ∈ [0, α c ] and s ∈ [0, 1], we define the following functions:

g(α, s) = 1 1 -α f π f -1 π (1 -α) -(1 -s) f π f -1 π (1 -α) f π (1) and ĝ(α, s) = ∂ s g(α, s) ∂ s g(α, 1
) .

There exists an implicit function α(ρ) defined on [0,

ρ π ] such that 1 -ρ = ĝ(α(ρ), 1 -ρ).
Then,

∀ε > 0, P H N N ≥ ρπ 0 u α (u) ∂ s ĝ(α(u), 1) du -ε -→ N →+∞ 1.
In addition, this bound still holds if we condition the graphs C (d (N ) ) to be simple by standard arguments.

Although the formulation of Theorem 1 is implicit, explicit computations are easy in specific models. Indeed, for d-regular random graphs with d ≥ 3 we find:

∀ε > 0, P   H N N ≥ d 2(d -1)   1 - 1 0 1 -x 1 d-1 1 -x 2 d-2 dx -ε     -→ N →+∞ 1.
For Erdős-Rényi random graphs with connection probability c/N (c > 1), denoting by ρ c the smallest positive solution of 1 -ρ c = exp(-cρ c ), we find:

∀ε > 0, P H N N ≥ ρ c -ln(1 -ρ c ) (γ + ρ c + ln(-ln(1 -ρ c )) -Li 2 (1 -ρ c )) -ε -→ N →+∞ 1,
where γ ≈ 0.577 . . . is Euler's constant and Li 2 is the dilogarithm function.

To the best of our knowledge, the only other general bound on H N is due to Frieze and Jackson in [START_REF] Frieze | Large holes in sparse random graphs[END_REF] in the setting where the degrees of the graph are bounded below by 3 and uniformly bounded above but do not necessarily satisfy our assumptions. For instance their lower bound for 3-regular graphs is approximately equal to 0.07 while our bound is approximately equal to 0.45. Their proof relies on a greedy algorithm which allows them to construct a macroscopic induced path in the graph. However, they do not establish the exact asymptotic length of this path, but rather a lower bound. Building on this result they also obtained a lower bound on H N /N for Erdős-Rényi random graphs having large fixed averaged degree.

To prove Theorem 1, we introduce a different algorithm, based on the depth first search algorithm, that is amenable to a detailed analysis with the framework developed in [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF] by the authors. This allows us to exhibit an induced path with explicit macroscopic length. As we will see in Section 4, it turns out that both algorithms provide the same long induced path (and cycle) up to o(N ) vertices. It is worth noting that simultaneously with our work, an algorithm similar to ours and the corresponding induced paths are studied by Draganic, Glock and Krivelevich [START_REF] Draganić | Short proofs for long induced paths[END_REF].

The paper is organized as follows. In Section 2 we present an algorithm that constructs a configuration model and spanning trees of its connected components for which ancestral lines form induced paths in the graph. We also state a result for the limiting profile of the spanning forest constructed by the algorithm in Theorem 2 from which Theorem 1 follows easily. In Section 3, we give a detailed analysis of our algorithm using the framework of our previous works [START_REF] Enriquez | Limiting shape of the depth first search tree in an Erdös-Rényi graph[END_REF][START_REF] Enriquez | Depth first exploration of a configuration model[END_REF]. In Section 4, we show the induced path constructed by our algorithm is roughly the same as the induced path constructed by the algorithm of Frieze and Jackson [START_REF] Frieze | Large holes in sparse random graphs[END_REF]. Finally, in Section 5, we analyse an extension of our algorithm. This extension mixes depth-first and breadth-first explorations and constructs m-induced paths for any fixed m.

Acknowledgments:

The first author would like to thank the ANR grants MALIN (Projet-ANR-16-CE93-0003) and PPPP (Projet-ANR-16-CE40-0016) for their financial support. The other three authors would like to thank the ANR grant ProGraM (Projet-ANR-19-CE40-0025) for its financial support. G.F. and L.M. also ackowledge the support of the Labex MME-DII (ANR11-LBX-0023-01).

Constructing the graph while discovering induced paths

We now introduce an algorithm which, from the knowledge of the sequence of degree d (N ) , simultaneously constructs a configuration model C (d (N ) ) together with an exploration of it. The latter exploration, which is a modification of the depth-first exploration, is designed to discover long induced paths in the graph. At each step n of the construction, we consider the following objects, defined by induction:

• A n , the set of active vertices, is an ordered list of pairs (v, m v ) where v is a vertex of V N and m v is an ordered list of elements of the form (u, (u 1 , . . . , u l )) where u is a vertex that will be matched to v and u 1 , . . . , u l vertices that will be matched to u during the exploration.

• S n , the set of sleeping vertices, which consists of vertices that do not appear in A n .

• R n , the set of retired vertices, which consists of vertices that appear neither in A n nor S n .

At the initial step n = 0 of the algorithm, we choose a vertex v uniformly at random and pair each of its d

(N ) v
half-edges to uniform half-edges of the graph. Denote by v 1 , . . . , v l the corresponding vertices. For each 1 ≤ i ≤ l, we successively match the half-edges of v i to uniform half-edges of the graph and denote by v 1 i , . . . , v ki i the corresponding vertices (without repeat). Let m v = (v 1 , (v 1 1 , . . . , v k1 1 )), . . . , (v l , (v 1 l , . . . , v k l l )) and set

     A 0 = ((v, m v )), S 0 = V N \ {v, v 1 , . . . , v l }, R 0 = ∅.
Suppose that A n , S n and R n are constructed. Three cases are possible:

1. If A n = ∅, the algorithm has just finished exploring and building a connected component of C (d (N ) ). In this case, we select v n+1 uniformly at random inside S n and define m vn+1 exactly as before, except that the matched vertices are in S n . Denoting v 1 n+1 , . . . , v l n+1 the vertices of S n matched to v n+1 , we then set:

     A n+1 = (v n+1 , m vn+1 ), S n+1 = S n \ {v n+1 , v 1 n+1 , . . . , v l n+1 }, R n+1 = R n . 2. If A n = ∅ and if its last element (v, m v ) is such that m v = ∅,
the exploration backtracks and we set:

     A n+1 = A n -(v, m v ), S n+1 = S n R n+1 = R n ∪ {v}.
3. If A n = ∅ and if its last element (v, m v ) is such that m v = ∅, we denote by (v n+1 , (v 1 n+1 , . . . , v l n+1 )) the first element of m v . In that case, the exploration goes to v n+1 and we construct m vn+1 as before using the v i n+1 's and the vertices of S n that are matched to them. We finally set:

     A n+1 = A n + (v n+1 , m vn+1 ), S n+1 = S n \ {v 1 n+1 , . . . , v l n+1 }, R n+1 = R n .
In words, this algorithm is an interpolation between depth-first and breadth-first explorations of the graph. More precisely, our procedure first constructs the 1-neighborhood of the current vertex v, which consists in some vertices v 1 , . . . , v l and it then matches sequentially the half-edges of v 1 , . . . , v l that are not yet matched. In particular, this ensures that every ancestral line of the trees constructed by the algorithm is in fact an induced path in the graph, because the discovered vertices

v j i , 1 ≤ i ≤ j, 1 ≤ j ≤ k i , are distinct from v 1 , . . . , v l .
Since each matching of half-edges is uniform during the construction, this algorithm constructs a random graph C (d (N ) ). Furthermore, at each step n, the subgraph of C (d (N ) ) induced by the vertices of S n is a configuration model. The sequence of vertices corresponding to the first component of the last element of A n provides a spanning tree of each connected component of the graph together with a contour process of each of these trees.

We will denote by (X n ) 0≤n≤2N the concatenated contour processes of the successive covering trees constructed by the algorithm. Our main result, Theorem 1, will be an easy consequence of the following fluid limit for the process (X n ) 0≤n≤2N : Theorem 2. Recall the definition of ρ π and ξ π given in equations (1) and (2), and the definition of the functions α(ρ), g(α, s) and ĝ(α, s) given in Theorem 1. Under assumptions (A1), (A2), (A3) and (A4), the following limit holds in probability for the topology of uniform convergence:

∀u ∈ [0, 2], lim N →∞ X uN N = h(u),
where the function h is continuous on [0, 2], null on the interval [2ξ π , 2] and defined hereafter on the interval [0, 2ξ π ].

The graph (u, h(u)) u∈[0,2ξπ] can be divided into a first increasing part and a second decreasing part. These parts are respectively parametrized for ρ ∈ [0, ρ π ] by :

       x ↑ (ρ) := ρπ ρ (2 -r) α (r) ∂ s ĝ(α(r), 1)
dr,

y ↑ (ρ) := ρπ ρ r α (r) ∂ s ĝ(α(r), 1)
dr,

for the increasing part and

   x ↓ (ρ) := x ↑ (ρ) + 2 (1 -α(ρ)) 1 -g α(ρ), 1 -ρ , y ↓ (ρ) := y ↑ (ρ),
for the decreasing part.

Theorem 1 is obtained by computing the maximal value of h, which is given by y ↑ (0). The proof of Theorem 2 is an adaptation of the article [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF] by the authors and is the object of the next section. It relies on Wormald's differential equations method [START_REF] Nicholas | Differential equations for random processes and random graphs[END_REF] via the study of ladder times of the exploration and the law of the graph induced by the sleeping vertices at these times.

Analysis of the algorithm

The overall strategy follows the guidelines of the previous work [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF]. In particular, we start by identifying a good event that makes possible a decomposition of the exploration at ladder times. For every n ∈ {0, . . . , 2N }, let D (N ) n be the degree of a uniform vertex in the graph induced by S n . For every ε > 0 we define

n = n (N ) ε = sup n ∈ 0, 2N : ∀m ∈ 0, n , E[D (N ) n (D (N ) n -1)] E[D (N ) n ] > 1 + ε .
For n < n ε , the subgraphs induced by S n are all supercritical. For

0 < δ < 1/2, let G ε = G (N )
ε (δ) be the event that, for all n < n ε ,

• there is at least one connected component with size greater than N 1-δ in the graph induced by S n ;

• there is no connected component of size between N δ and N 1-δ in the graph induced by S n .

Under our assumptions (A1), (A2), (A3) and (A4), we have for every λ > 0,

P G ε = 1 -O(N -λ ). (3)

Ladder times

Fix δ ∈ (0, 1). Let T 0 = 0 and define, for k ∈ {0, . . . , K},

T k+1 := min i > T k , X i = k + 1 and ∀i ≤ j ≤ i + N δ , X j ≥ k + 1 ,
where K is the last index for which this definition makes sense (i.e. the set for which the min is taken is not empty). Of course, this sequence of times will only be useful to analyse our algorithm when K is of macroscopic order, which is indeed the case on the event G ε . Indeed, as long as T k < n ε , we can define T k+1 on the event G ε . Therefore we set

K ε = sup{k ∈ 0, K : T k < n ε }. (4)
Thanks to (3), we have For all k ∈ {0, . . . , K}, let v k be the vertex corresponding to the first component of the last element of A T k . There exists some l ≥ 1 such that the sequence m v k can be written

K ε < K with probability 1 -O(N -λ ). S k S Tk v k v k+1 S k+1 u 1 u 2 u ek = u 3
m v k = (u 1 , (u 1 1 , . . . , u k1 1 )), . . . , (u l , (u 1 l , . . . , u k l l )) , (5)
and we will denote by e k the index in {1, . . . , l} such that u e k +1 = v k+1 . We consider S k the graph induced by the set of vertices S T k -1 . See Figure 1 for an illustration of these definitions.

As it turns out, the analysis of the structural changes of S k will be crucial for our purpose. For instance, the difference between T k+1 -T k is equal to the time spent exploring the connected components associated to the vertices u 1 , . . . , u e k inside the graph S k .

Analysis of the graphs S k

For all k < K, let N i (k) be the number of vertices of degree i in S k ∪ {v k } which are different from v k . Then, by definition of the exploration, the graph S k has the law of a configuration model with vertex degrees given by the sequence ( N i (k)) i≥0 . Using the notation of (5), the contribution to N i (k) of the edges belonging to v k is given by

l p=1 -1 deg S k (up)=i + 1 deg S k (up)=i-1 ,
and we write

N i (k) = N i (k) + l p=1 -1 deg S k (up)=i + 1 deg S k (up)=i-1 .
Assumption (A4) ensures that N i (k)-N i (k) is of order o(N ) uniformly along the whole exploration with high probability. Henceforth, we focus our analysis on the N i (k)'s whose analysis is more clear. This evolution is ideed given by:

N i (k + 1) -N i (k) = -V i (S k \ S k+1 ) (6)
+ l p=e k +2 kp q=1 -1 deg S k (u q p )=i + 1 deg S k (u q p )=i+1 , (7)
where V i (S) stands for the number of vertices with degree i in S and l is defined in Equation [START_REF] Frieze | Large holes in sparse random graphs[END_REF]. Indeed, the first contribution corresponds to the complete removal of vertices belonging to S k but not S k+1 . The second contribution corresponds to the removal of edges connecting the vertices u e k +2 , . . . , u l to S k+1 . The crucial step of the proof is the asymptotic analysis of the variables T k and N i (k) for large N . This is the object of the forthcoming Theorem 3. In order to state it, we first need to introduce some notation.

Let (z i ) i≥0 ∈ R Z+ be such that i≥0 z i ≤ 1 and k≥0 iz i < ∞. for any i ≥ 0 let ẑi = (i + 1)z i / j jz j and define:

     g (zi) i≥0 (s) = i≥0 zi l≥0 z l s i ĝ(zi) i≥0 (s) = i≥0 ẑi s i = g (z i ) i≥0
(s)

g (z i ) i≥0 (1) (8)
respectively the generating series associated to (z k ) k≥0 and its sized biased version. Let also ρ (zi) i≥0 be the largest solution in [0, 1] of

1 -s = ĝ(zi) i≥0 (1 -s). (9)
Remark 1. Since ĝ is the generating function of a probability distribution on the integers, it is convex on [0, 1]. Therefore, Equation (9) has a positive solution in (0, 1] if and only if ĝ (1) > 1,

which is equivalent to l≥1 (l-1)lz l l≥1 lz l > 1.

We also define the following functions:

f (z 0 , z 1 , . . .) = 2 -ρ (zi) i≥0 ρ (zi) i≥0 (10)
f i (z 0 , z 1 , . . .) = - 1 ρ (zj ) j≥0 iz i j≥0 kz j + 1 ρ (zj ) j≥0 j≥0 (j -1)jz j n≥0 jz j -1 × - iz i j≥0 jz j + j≥0 (j -1)jz j n≥0 jz j (i + 1)z i+1 j≥0 jz j - iz i j≥0 jz j . ( 11
)
The asymptotic behaviour of the variables T k and N i (k) will be driven by the solution of an infinite system of differential equations whose uniqueness and existence is provided by the following lemma.

Lemma 1. Let π = (π i ) i≥0 ∈ [0, 1] N be a probability measure which satisfies the supercriticality assumption (A2). Then, the following system of differential equations has a unique solution which is well defined on [0, t max ) for some t max > 0:

dzi dt = f i (z 0 , z 1 , . . .); z i (0) = π i . (S) Proof. Let F (t, s) := i≥0 z i (t)s i (12)
be the generating series associated to the z i 's, which is well defined for all s ∈ [0, 1] and all t ∈ [0, t max ), where [0, t max ) is the maximal interval where the functions z i are well defined. Then, it is easy to check that F satisfies the following partial differential equation:

∂F ∂t (t, s) = 1 ρ (zj (t)) j≥0 ∂ 2 F ∂s 2 (t, 1) ∂F ∂s (t, 1) ∂F ∂s (t, s) ∂F ∂s (t, 1) (1 -s) ∂ 2 F ∂s 2 (t, 1) ∂F ∂s (t, 1) -1 .
Using the appropriate time change, we end up with a new generating series

f (t, s) = j≥0 ζ j (t)s i satisfying ∂f ∂t (t, s) = ∂f ∂s (t, s) ∂f ∂s (t, 1) (1 -s) ∂ 2 f ∂s 2 (t, 1) ∂f ∂s (t, 1) -1 . ( 13
)
Notice that, up to a time change, this corresponds to the differential equation that already appeared in [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF] -see the beginning of the proof of Proposition 1. It was proved in Section 6.2 of [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF] that it has a unique solution under our assumptions.

We are now ready to state the main result of this section.

Theorem 3. Fix ε > 0. With high probability, for all k ≤ K ε :

T k = N z k N + o(N ) N i (k) = N z i k N + o(N ),
where (z 0 , z 1 , . . .) is the unique solution of (S) and z is the unique solution of dz dt = f (z 0 , z 1 , . . .) with initial condition given by z(0) = 0.

In addition, if w(k) denotes the number of vertices that are not in the graph S k , then

w(k) = N z k N + o(N ),
where z satisfies z (t) = ĝ (zj (t)) j≥0 (1)/ρ (zj (t)) j≥0 and z(0) = 1.

Proof. Our main tool is an adaptation of Wormald's differential equations method, which is the content of Corollary 2 of [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF]. To apply this result we need to check the following two points:

1. There exists 0 < β < 1/2 such that with high probability for all k ≤ K ε ,

|T k+1 -T k | ≤ N β and for all i ≥ 0, |N i (k + 1) -N i (k)| ≤ N β .
2. We denote by (F k ) k≥0 the canonical filtration associated to the sequence ((N i (k)) i≥0 ) k≥0 . There exists λ > 0 such that for every k and n,

E[T k+1 -T k | F k ] = f N 0 (k) N , N 1 (k) N , . . . + O N -λ , (14)
E[N i (k + 1) -N i (k) | F k ] = f i N 0 (k) N , N 1 (k) N , . . . + O N -λ . ( 15
)
The first point is a direct consequence of the definition of the times T k 's and of Equation ( 3) by chosing δ small enough.

We now turn to the second point. Since the computations are very similar to those made during the proof of Theorem 3 of [3], we will only sketch them and point out the corresponding details in [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF]. For all k ≥ 0, let

p i = p i (k) = Ni(k) j≥0 Nj (k) ; g k = g (pj ) j≥0 pi = pi (k) = (i+1)pi+1(k) j≥0 jpj (k) ; ĝk = ĝ(pj) j≥0 = g ( pj ) j≥0 , (16)
and let ρ k = ρ (pj (k)) j≥0 be the largest solution in [0, 1] of 1 -s = ĝk (1 -s).

Recall the notation of ( 5). With high probability, the first e k neighbors of v k belong to distinct connected components of S k . Denoting W (1) , . . . , W (k) these connected components, we deduce that

E[T k+1 -T k | F k ] = 1 + 2E   k j=1 |W (j) | F k   = 2 -ρ k ρ k + O(N -λ ),
where the last equality is the content of Equation ( 12) in [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF]. This proves (14). We now fix i ≥ 0, k ≥ 0, and prove (15) by examining separately the contributions ( 6) and ( 7). The contribution (6) corresponds to the removal of vertices of degree i inside the small components W (j) 's, to the removal of v k+1 , and to the removal of u e k +2 , . . . , u l . It is given by

E [V i (S k \ S k+1 ) | F k ] = E V i ∪ e k j=1 W (j) | F k + P(deg S k (v k+1 ) = i | F k ) + E l j=e k +2 1 {deg S k (uj )=i} | F k (17)
The terms E V i ∪ e k j=1 W (j) | F k and P(deg

S k (v k+1 ) = i | F k )
were respectively computed in Equations ( 14) and (10) of [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF]. They are given by

E V i ∪ e k j=1 W (j) | F k = p i-1 ρ k (1 -ρ k ) i-1 + O(N -λ ) (18)
P(deg S k (v k+1 ) = i | F k ) = pi-1 ρ k 1 -(1 -ρ k ) i-1 + O(N -λ ). (19)
For the last term, we use that with high probability, u e k +2 , . . . , u l are distinct vertices. All of them are connected to v k through a uniform matching of half-edges. Therefore:

E l j=e k +2 1 {deg S k (uj )=i} F k = E deg S k (v k ) -e k -1 | F k pi-1 + O(N -λ ) = 1 ρ k (ĝ k (1) -1) pi-1 + O(N -λ ). ( 20
)
where the computation of

E deg S k (v k ) -e k -1 | F k can be found in Equation (15) of [3].
Finally, the contribution ( 7) is given by

E l p=e k +2 kp q=1 -1 deg S k (u q p )=i + 1 deg S k (u q p )=i+1 F k = E deg S k (v k ) -e k -1 | F k ĝ k (1) (-p i-1 + pi ) + O(N -λ ) = 1 ρ k (ĝ k (1) -1) ĝ k (1) (-p i-1 + pi ) + O(N -λ ) (21)
Combining ( 18), ( 19), ( 20) and ( 21) we obtain

E [N i (k + 1) -N i (k) | F k ] = ĝ k (1) ρ k (-p i-1 ĝ k (1) + pi (-1 + ĝ k (1))) + O(N -λ ) (22)
giving Equation (15).

We finally turn to the last claim of Theorem 3. For all k < K ε , let w(k) be the number of vertices that are not in the graph S k . Using the notation of ( 5), the evolution of w(k) is given by

w(k + 1) -w(k) = V (S k \ S k+1 ) = V ∪ e k j=1 W (j) + 1 + (l -e k -1).
Therefore,

E [w(k + 1) -w(k) | F k ] = 1 -ρ k ρ k + 1 + 1 ρ k (ĝ k (1) -1) = 1 ρ k ĝ k (1). (23)
Using Wormald's differential equations method as before we deduce that with high probability

w(k) = N z(k/N ) + o(N ),
where z is the only solution of y (t) = ĝ (zj (t)) j≥0 (1)/ρ (zj (t)) j≥0 with initial condition y(0) = 1.

The asymptotic degree distribution inside S k

As in [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF], Theorem 3 allows us to identify the laws of the graphs induced by sleeping vertices remaining after having explored a given proportion of vertices. Remarkably, these laws are the same as the laws appearing in the Depth First Search algorithm in Theorem 1 of [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF]. We will see in the next section that the speed at which the graph is explored is however different. Proof. Fix α ∈ [0, α c ), by definition, a configuration model with asymptotic degree distribution π α is supercritical. Therefore,

E D τ (N ) (α) (D τ (N ) (α) -1) E D τ (N ) (α) > 1 + ε
for some ε > 0 and N large enough, which ensures that τ (N ) (α) < n ε . By definition of z, this also ensures that N z-1 (α) < K ε and that the proportion of explored vertices at time

T N z-1 (α) is αN + o(N ). Therefore, τ (N ) (α) = inf{n ≥ 0, |S n | ≤ (1 -α)N } = T N z-1 (α) + o(N ) and for all i ≥ 0, V i S τ (N ) (α) = N i T N z-1 (α) + o(N ) = N z i z-1 (α) + o(N ).
It is easy to check that the generating series associated to the sequence of functions (z i • z-1 ) i≥0 is solution to the partial differential equation (13).

Proof of Theorem 2

Let N ≥ 1. By definition, for all 1 ≤ k ≤ K ε , the contour process of the tree constructed by our algorithm at time T k is located at point (T k , k). Furthermore, by Theorem 3,

(T k , k) = N z k N + o(1), k N .
Note that |T k+1 -T k | = o(N ) and that, between two consecutive T k 's, the contour process cannot fluctuate by more than o(N ). Hence, after normalization by N , in its increasing part the limiting contour process converges to the curve (z(t), t) where t ranges from 0 to t max = sup{t > 0, z (t) < +∞}. In the remaining, we provide a parametrization (x ↑ (ρ), y ↑ (ρ)) ρ∈(0,ρπ] of this increasing curve. Recalling the definition of f given in Equation (10), our Theorem 3 gives us

(x ↑ ) (ρ) (y ↑ ) (ρ) = 2 ρ -1.
exactly as in [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF].

To obtain a second equation involving (x ↑ ) (ρ) or (y ↑ ) (ρ), the paper [START_REF] Enriquez | Depth first exploration of a configuration model[END_REF] uses the implicit function α(ρ) given by the only solution of 1-ρ = ĝ(α, 1-ρ). The link between α, x ↑ , y ↑ is however different in our setting. In order to establish this link, let us first notice that ρ(t) = ρ (zi(t)) i≥0 t is the fluid limit of the survival probability (ρ k ) k as N tends to infinity, where we recall that the ρ k 's are defined in terms of the functions g k (see Equation ( 16)). Indeed, since for all t ≥ 0, we have

1 -ρ tN = ĝ tN (1 -ρ tN ),
the fact that the sequence of generating series (ĝ tN (s)) N ≥0 converges to ∂ s F (t, s)/∂ s F (t, 1) (recall that F is defined in Equation ( 12)) as N tends to infinity and an application of Dini's Theorem ensures that ρ tN converges to ρ(t). For all N ≥ 0, we define the function α (N ) by

∀ρ ∈ (0, ρ π ], α (N ) (ρ) = 1 - |S k(ρ) | N where k(ρ) = argmin 0≤k≤N {|1 -ρ -ĝk (1 -ρ)|}.
From this definition, it is clear that α (N ) converges to the implicit function α. Moreover, by definition of w in Section 3.3, we have that

∀k ∈ 0, K ε , w(k) = N α (N ) (ρ k ),
giving that z(t) = α(ρ(t)). On the other hand, using Theorem 3, we deduce that

d dt z(t) = 1 ρ(t) ∂ s ĝ(α(ρ(t)), 1),
which finally yields

y (ρ) = ρα (ρ) ∂ s ĝ(α(ρ), 1) . ( 24
)
The decreasing part, is obtained by translating horizontally each point (x ↑ (ρ), y ↑ (ρ)) of the ascending phase to the right by twice the asymptotic proportion of the giant component of the remaining graph of parameter ρ, which is 2(1 -g(α(ρ), 1 -ρ)). Indeed, the time it takes to the DFS to return at a given height k attained during the ascending phase corresponds to the time of exploration of the giant component of the unexplored graph at time T k . The latter is given by twice the number of vertices of the giant component which is equal to 2(1 -g k (1 -ρ k )).

From induced paths to induced cycles

We are going to show that, with high probability, one of the first vertices of the spine of the tree constructed by our algorithm shares a common neighbor with one of the last vertices of the spine Figure 2: Left: an induced cycle constructed by the algorithm in green. Center: a matching to a half edge of E ε for a vertex that is not on the spine. Right: a matching to a half edge of E ε for a vertex of the spine. and that this common neighbor is not connected to another vertex of the spine. See Figure 2 left for an illustration. This ensures that our bound on the length of the longest induced path is also valid for the longest induced cycle.

Recall the definition of the ladder times T k , of the associated vertices v k on the spine of the tree and of m v k = (u 1 , (u 1 1 , . . . , u k1 1 )), . . . , (u l , (u 1 l , . . . , u k l l )) given in Equation ( 5). The candidates for a common neighbor between vertices of the spine are u e k +2 , . . . , u l (recall that u e k +1 = v k+1 ). These vertices are connected to v k and to a half edge of each of the vertices u j i for i ∈ e k + 2, l . The induced cycles we are interested in are when one of these vertices u j i is on the spine of the tree. We denote E k the set of half edges of the vertices u j i for i ∈ e k + 2, l not yet matched. For ε > 0 small enough, the number of half edges of E ε = εN k=1 E k that are still unmatched at time T εN is larger than ηN for some η > 0. For εN ≤ k ≤ K ε , we denote by η k N the number of half edges of E ε that are still unmatched at time T k and such that the corresponding vertex has not been connected to a vertex of the spine between heights εN and k. The evolution of η k can be studied with Wormald's differential equation method in a similar fashion as in the proof of Theorem 3. We have:

E [η k+1 N -η k N |F k ] ≥ - 1 -ρ k ρ k + 1 ρ k (ĝ k (1) -1) ĝ 0 (1) 1 -ĝ0 (0) + ĝ 0 (1) 1 -ĝ0 (0) 2 η k N |S k | g k (1) + O N -λ .
Indeed, each new matching of the algorithm has a probability η k N |S k | g k (1) to be with an available half edge of E ε . The first term

1-ρ k ρ k + 1 ρ k (ĝ k (1) -1) ĝ 0 (1)
1-ĝ0(0) corresponds to the number of matchings along the exploration between T k and T k+1 , except for the matching of v k and v k+1 (see Figure 2, center). For such matchings, we have to remove every other half edge of the discovered vertex from E ε , whose expected number is roughly the expectation of π conditioned to be nonzero since it was fixed at the very begining of the construction (note that these half edges are still available for the construction). If v k and v k+1 are matched by a half edge of E ε , this means that v k+1 is a neighbor of a vertex u at distance 1 from the first εN first vertices of the spine. In this case, we have to remove from E ε every half edge of v k+1 and every half edge of E ε belonging to a vertex connected to u (see Figure 2, right). The expectation of the number of these removed edges is bounded from above by the square expectation of π conditioned to be non 0 (since some some half edges may have been matched previously).

As long as k ≤ K ε , the factor in front of η k in the above equation is uniformly bounded in absolute value by a finite constant c ε depending of ε. This ensures that (η tN ) t is stochastically dominated by a process that has a fluid limit that is smaller than the solution of the differential equation y = -c ε y as long as t < K ε /N , thus η Kε > η exp(-c ε t max ) with high probability.

We established that at the ladder time T Kε , with high probability, at least η exp(-c ε t max )N available half edges that belong to some vertex u are such that:

• The vertex u is connected to a vertex u which is itself connected to the spine at height lower than εN . • The vertex u is not connected to any vertex of the spine between heights εN + 1 and K ε .

For k > K ε , each vertex of the spine v k has a probability roughly η exp(-cεtmax)

|S k |/N
= O(1) to form with E ε an induced cycle of length at least K ε -εN . Taking first the limit N → ∞ and then ε → 0 proves that our algorithm constructs an induced cycle of the same macroscopic length as the spine.

Comparison with Frieze and Jackson's algorithm

In [START_REF] Frieze | Large holes in sparse random graphs[END_REF], Frieze and Jackson study the following variant of the Depth-First algorithm that constructs a subtree of each connected component of the graph: Perform a depth-first exploration of the graph, and each time a new vertex is discovered, ask if it is connected to a vertex belonging to its ancestral line in the exploration tree. If it is the case, delete this vertex from the exploration tree and backtrack. The ancestral lines of trees constructed by this algorithm are induced paths by construction, however they are not necessarily spanning trees of the corresponding connected components.

Our algorithm and Frieze and Jackson's algorithm do not, in general, provide the same induced paths on some deterministic examples of graphs. However, for configuration graphs satifying assumptions (A1), (A2), (A3), (A4), with high probability, they will construct two trees with identical spines up to a microscopic number of vertices at the top. To see this, we first construct the graph and our tree with the algorithm of Section 2, and then perform Frieze and Jackson's algorithm on the resulting graph and starting at the same initial vertex of the giant component. The construction of the gives a total order on its vertices according to their first appearance in the contour of the spanning tree. We use this order to choose between neighbors in the DFS performed by Frieze and Jackson.

Fix ε > 0. The following statement on the Frieze and Jackson's algorithm can be proved by induction. With high probability, for all k < K ε ,

• The exploration goes from v k to v k+1 , • The vertices explored between the first visit of v k and the first visit of v k+1 form a subset of the vertices explored between the times T k and T k+1 of our algorithm.

Indeed, if Frieze and Jackson's algorithm visits v k , at the first visit of this vertex, the vertices that have not been explored by this algorithm are the vertices of S k , a subset of the vertices that our algorithm has explored before time T k , and the vertices attached to the spine before v k . The vertices already explored by our algorithm that are still available for Frieze and Jackson's algorithm belong to small connected components inside past graphs S i for some i < k and will never be explored by Frieze and Jackson's algorithm. The vertices attached to the spine form cycles in the graph. They are therefore deleted if explored by Frieze and Jackson's algorithm. Thus, after the first visit of v k , the vertices that are truly available for Frieze and Jackson's algorithm are the vertices of S k and the induction follows.

Finally, from v Kε , Frieze and Jackson's algorithm explores a subgraph of S Kε and the length of the induced path cannot be increased by more than the size of its giant component. This giant component has a size C ε N with C ε → 0 as ε → 0.

Extension to m-induced cycles

Let m ≥ 1. An m-induced cycle inside a given graph G is a cycle such that two vertices separated by k edges of the cycle have a distance at least min{m, k} in the graph G. When m = 1, we retrieve the definition of induced cycles. In this last section, we briefly explain how to adapt our arguments in order to find the following lower bound on the length of the longest m-induced cycle in a configuration model:

Proposition 1. Let H m
N be the length of the longest m-induced cycle in in C (d (N ) ) satisfying assumptions (A1), (A2), (A3), (A4). Then,

∀ε > 0, P H m N N ≥ m ρπ 0 u α (u) m j=1 (∂ s ĝ(α(u), 1)) j du -ε -→ N →+∞ 1.
Proof. This bound comes from the following generalization of the algorithm defined in Section 2.

The idea is to interpolate between a depth-first and a breadth-first exploration. Each the exploration goes to a new vertex v, it discovers its m-neighborhood by a breadth-first exploration creating a rooted plane tree T v with root v and height at most m. We denote by v 1 , . . . , v l the vertices of height m in T v listed in lexicographic order (that is in order of their discovery).

Similarly as for in Section 2, for each 1 ≤ i ≤ l, we successively match the half-edges of v i to uniform half-edges of the graph and denote by v 1 i , . . . , v ki i the corresponding vertices and write

m v = (v 1 , (v 1 1 , . . . , v k1 1 )), . . . , (v l , (v 1 l , . . . , v k l l )
) . The evolution of active and sleeping vertices follows the same rules as before except that when a new vertex v is explored, every vertex of the tree T v is removed from the set of sleeping vertices. can define similar ladder times (T k ) for when the exploration discovers a vertex v k of the giant component of the graph induced by the sleeping vertices. We denote by w k,0 = v k ; w k,2 . . . ; w k,m = v k+1 the ancestral line between v k and v k+1 . Between T k and T k+1 , the algorithm explores completely the connected components of the vertices on the left hand side of this ancestral line, and up to a distance between m and 1 for the right hand side (see Figure 3 for an illustration). Fix m between 0 and m -1 and denote u 1 , . . . , u l the children of w k,m in T v k . Let e m be such that u e m +1 = w k,m +1 . For j ≤ e m , we also denote by W (j) the connected components of u j explored by the algorithm. Finally, for j > e m + 1, we denote by T v k (u j ) the subtree of T v k emanating from u j . The contribution of vertices attached to w k,m to the evolution of vertices of degree i is given by: Summing for m between 0 and m -1 finally gives:

v k v k+1 w k,2 W (1) W (2) u 1 u 2 u 3 u 4 T v k (u 4 ) T v k
∆ i (w k,m ) = -V i ∪
E [N i (k + 1) -N i (k) | F k ] = m j=1 (ĝ k (1)) j ρ k (-p i-1 ĝ k (1) + pi (-1 + ĝ k (1))) + O(N -λ ).
Using the same arguments as in the proof of Theorem 3, we deduce that for all i ≥ 0, the function t → N i ( tN )/N converges pointwise towards a function z i with high probability. The corresponding sequence of functions (z i ) i≥0 is the unique solution of an infinite system of differential equations, and their generating series F (t, s) = i≥0 z i (t)s i satisfies the following Up to a time change, this is exactly Equation 12. As it turns out, the resulting new time scale corresponds to the proportion of explored vertices during the exploration of the graph whose derivative is given by the analog of Equation 23 which amounts here to the prefactor: The contour process of the spanning tree constructed by this new algorithm has therefore a fluid limit with two parametrized arcs (x ↑ (ρ), y ↑ (ρ)) and (x ↓ (ρ), y ↓ (ρ)) as in Theorem ??. The derivative of y ↑ is given by

(y ↑ ) (ρ) = m • ρ α (ρ)
m j=1 (∂ s ĝ(α(ρ), 1)) j which is the analog of Equation (24) in the current setting. Notice the factor m which comes from the fact that the ancestral line between two vertices v k and v k+1 has length m.

Figure 1 :

 1 Figure 1: Structure of the remaining graph at a ladder time. The first half edges of v k are numbered according to their matching order during the construction.

Theorem 4 .

 4 Recall the definition of α c and of g(α, s) given in Theorem 1. For every α ∈ [0, α c ], let π α be the probability distribution on Z + with generating series g(α, s). Then, for every α ∈ [0, α c ], denoting τ (N ) (α) = inf{n ≥ 1, |S n | ≤ (1 -α)N }, the empirical degree distribution of the graph induced by the vertices of S τ (N ) (α) converges to π α .

Figure 3 :

 3 Figure 3: Illustration of the proof of Proposition 1 for m = 4 and m = 2. Dotted lines are explored between times T k and T k+1 .

( 1 )

 1 e m j=1 W (j) -1 {deg(w k,m +1 )=i} -x∈Tv k (ue m +2)∪•••∪Tv k (u l ) 1 deg(x)=i + x∈∂Tv k (ue k +2)∪•••∪∂Tv k (u l ) -1 deg(x)=i + 1 deg(x)=i+1 .Computations analogous to those made during the proof of Theorem 3 yieldE [∆ i (w k,m ) | F k ] = --1) (ĝ k (1)) m-m (p i-1 -pi ) + O(N -λ ).Simplifying the above expression, we obtain an equation similar to (22) :E [∆ i (w k,m ) | F k ] = pi-1 ρ k -(ĝ k (1)) m-m +1 + pi ρ k (ĝ k (1)) m-m (-1 + ĝ k (1)) + O(N -λ ) = (ĝ k (1)) m-m ρ k (-p i-1 ĝ k (1) + pi (-1 + ĝ k (1))) + O(N -λ ).