2019/11/22 by Nathanaël Enriquez, Enriquez, Nathanaël, Gabriel Faraud +5
Mathematics · #60F10 #60J20 #60K35 #82C21 #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · doi:10.48550/arxiv.1911.10083
openalex publication_date 2019/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce an algorithm that constructs a random uniform graph with prescribed degree sequence together with a depth first exploration of it. In the so-called supercritical regime where the graph contains a giant component, we prove that the renormalized contour process of the Depth First Search Tree has a deterministic limiting profile that we identify. The proof goes through a detailed analysis of the evolution of the empirical degree distribution of unexplored vertices. This evolution is driven by an infinite system of differential equations which has a unique and explicit solution. As a byproduct, we deduce the existence of a macroscopic simple path and get a lower bound on its length.