Premium
Random cographs: Brownian graphon limit and asymptotic degree distribution
Author(s) -
Bassino Frédérique,
Bouvel Mathilde,
Féray Valentin,
Gerin Lucas,
Maazoun Mickaël,
Pierrot Adeline
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21033
Subject(s) - mathematics , combinatorics , vertex (graph theory) , random graph , discrete mathematics , degree distribution , weak convergence , degree (music) , limit (mathematics) , graph , complex network , computer science , mathematical analysis , physics , computer security , acoustics , asset (computer security)
We consider uniform random cographs (either labeled or unlabeled) of large size. Our first main result is the convergence toward a Brownian limiting object in the space of graphons. We then show that the degree of a uniform random vertex in a uniform cograph is of order n , and converges after normalization to the Lebesgue measure on [ 0 , 1 ] . We finally analyze the vertex connectivity (i.e., the minimal number of vertices whose removal disconnects the graph) of random connected cographs, and show that this statistics converges in distribution without renormalization. Unlike for the graphon limit and for the degree of a random vertex, the limiting distribution of the vertex connectivity is different in the labeled and unlabeled settings. Our proofs rely on the classical encoding of cographs via cotrees. We then use mainly combinatorial arguments, including the symbolic method and singularity analysis.