Graphon Limits of Static and Dynamic Models of Random Cographs
Informal Systems Seminar
Speaker: – CNRS Tenured Research Scientist, Institut Elie Cartan de Lorraine (IECL), France
Ìý
Abstract: 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.
