Encoding the size of the connected components and number of surplus edges of random graphs

par Josué Corujo (LAMA - UPEC)

mardi 7 nov. 2023, 14:15 → 15:15 Europe/Paris

UTC - GI

In this presentation, we will delve into an inhomogeneous random graph process that incorporates vertex sizes and edges emerging at exponential times with rates equal to the product of the vertices sizes. We will show how this model serves as a natural extension of the classic Erdös-Rényi random graph. Then, we will explore a generalization of a graph exploration process known as the simultaneous breadth-first walk (as introduced by V. Limic in 2019). We will clarify how this extension enables us to encode essential information related to both the sizes of connected components and the number of surplus edges. This encoding represents a solid first step towards a new and simpler understanding of the scaling limits of these processes.

This talk is based on a work in collaboration with Vlada Limic (CNRS, Université de Strasbourg) contained in the preprint:
- J. C., Vlada Limic (2023) A dynamical approach to spanning and surplus edges of random graphs arXiv:2305.04716