Video URL

https://old.simons.berkeley.edu/node/22606

Graphon Limit and Large Independent Sets in Uniform Random Cographs

(2022). Graphon Limit and Large Independent Sets in Uniform Random Cographs. The Simons Institute for the Theory of Computing. https://old.simons.berkeley.edu/node/22606

Graphon Limit and Large Independent Sets in Uniform Random Cographs. The Simons Institute for the Theory of Computing, Sep. 29, 2022, https://old.simons.berkeley.edu/node/22606 

          @misc{ scivideos_22606,
            doi = {},
            url = {https://old.simons.berkeley.edu/node/22606},
            author = {},
            keywords = {},
            language = {en},
            title = {Graphon Limit and Large Independent Sets in Uniform Random Cographs},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {sep},
            note = {22606 see, \url{https://scivideos.org/index.php/simons-institute/22606}}
          }
Valentin Féray (Université de Lorraine)
Source Repository Simons Institute
Subject

Abstract

Abstract   Cographs are by definition $P_4$-free graphs, i.e. graphs avoiding the path $P_4$ as induced subgraph. In this talk, we will consider a uniform random cograph with $n$ vertices, for large $n$. We shall describe the (random) graphon limit of this object, which is constructed using a Brownian excursion. Motivated by some probabilistic work around Erdős-Hajnal conjecture, we also consider large independent sets in uniform cographs. For both aspects, cographs behave differently from most other $H$-free random graphs. Based on joint work with F. Bassino, M. Bouvel, M. Drmota, L. Gerin, M. Maazoun and A. Pierrot.