The depth first search exploration of a supercritical configuration model

We consider large random graphs with a given degree sequence. In the sparse regime where the degree sequence converges to a probability distribution, the model has a phase transition for the existence of a macroscopic connected component. In this talk, we will study the depth first search algorithm in the supercritical regime. In particular, we will see that the evolution of the empirical degree distribution of the unexplored vertices has a fluid limit which is driven by an infinite system of differential equations. Surprisingly, this system admits an explicit solution in terms of the initial degree distribution. This in turn allows to prove that the renormalised contour process of the exploration has a deterministic profile for which we can give an explicit parametric representation. The height of this curve gives information about long simple paths in the graph.