Abstract:
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. Based on joint works with N. Enriquez, G. Faraud and N. Noiry. Everything will be defined/introduced during the talk.
Biography:
Laurent Ménard is a Visiting Associate Professor of Mathematics at NYU Shanghai. He is also an Assistant Professor at Université Paris Nanterre (former Paris 10). Ménard graduated from the École Normale Supérieure in Paris before receiving his PhD in Mathematics at the Université Pierre et Marie Curie (Sorbonne Université). His main research interests are in Probability Theory and Combinatorics.
Seminar by the NYU-ECNU Institute of Mathematical Sciences at NYU Shanghai