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.
Date: 21 November 2019, 10:00
Venue: 24-29 St Giles', 24-29 St Giles' OX1 3LB
Venue Details: Department of Statistics, LG.01 (Large Lecture Theatre)
Speaker: Laurent Ménard (Université Paris Nanterre)
Organising department: Department of Statistics
Organisers: Christina Goldschmidt (Department of Statistics, University of Oxford), James Martin (Department of Statistics, University of Oxford)
Part of: Probability seminar
Booking required?: Not required
Audience: Public
Editor: Christina Goldschmidt