Graphs with prescribed modular decomposition, Convergence in the sense of graphons, and number of induced subgraphs

by Théo Lenoir

Thursday Jun 19, 2025, 2:00 PM → 3:00 PM Europe/Paris

435 (ENS Lyon)

The goal of this talk is to explain the behavior of certain types of specific graph models, in particular models of graphs with forbidden patterns. To do so, we will introduce the modular decomposition, a tool that is relatively well-known in algorithmics, but whose study from a probabilistic perspective has only begun very recently. We will then see how, for a broad class of models defined by various constraints on the modular decomposition, one can determine the density of each graph as an induced subgraph. This result implies convergence in the sense of graphons, which can be seen as a kind of convergence of adjacency matrices. Specifically, we observe the convergence of a graph of size n towards a “continuous” graph, known as the Brownian cographon, which can be constructed from a Brownian excursion.