Retour aux activités
Séminaire informel de théorie des systèmes (ISS)

Graphon Limits of Static and Dynamic Models of Random Cographs


12 mai 2023   12h00 — 13h00

Valentin Féray Chargé de recherches CNRS, Institut Elie Cartan de Lorraine (IECL), France

Valentin Féray

Lien pour le webinaire.

By definition, cographs are graphs that can be obtained starting from the one-vertex graph by iterating the following "duplication" operation: choose a vertex, duplicate it (the new vertex has the same neighbours as the original vertex), and possibly connect by an edge the new vertex to the original one. Cographs enjoy many equivalent characterizations (e.g.~they are exactly the graphs avoiding the path P_4 as induced subgraph) and have been well-studied from an algorithmic point of view (many NP hard problem are tractable when the input is assumed to be a cograph).

In this talk we discuss the asymptotic property of large random cographs, in particular their limit in the sense of graphons. We will consider three different models of random cographs: a static one (uniform distribution on cographs with $n$ vertices), a dynamic one with growing size (where duplications are applied at random starting from the one vertex graph) and a dynamic one with constant size (where duplications and vertex deletions are applied at random starting from any graph with $n$ vertices).

Based on joint works with F. Bassino, M. Bouvel, L. Gerin, M. Maazoun, A. Pierrot and K. Rivera-Lopez.

Biography: Valentin Féray received his Ph.D. in Mathematics from University Paris-Est Marne-La-Vallée (advisor : Philippe Biane). He is currently a CNRS tenured research scientist at IECL, Nancy. Before that he was an Assistant professor of Pure Mathematics at the University of Zurich and a CNRS tenured research scientist in LaBRI, Bordeaux. In 2013, he gave the Cours Peccot at College de France.

Peter E. Caines responsable
Aditya Mahajan responsable
Shuang Gao responsable
Borna Sayedana responsable


Montréal Québec

Organisme associé

Centre for intelligent machines (CIM)

Axes de recherche