Premium
Graphon convergence of random cographs
Author(s) -
Stufler Benedikt
Publication year - 2021
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.21002
Subject(s) - combinatorics , infinity , mathematics , random graph , limit (mathematics) , random tree , tree (set theory) , convergence (economics) , discrete mathematics , computer science , graph , artificial intelligence , mathematical analysis , motion planning , robot , economics , economic growth
We study the behavior of random labeled and unlabeled cographs with n vertices as n tends to infinity. We show that both models admit a novel random graphon W 1/2 as distributional limit. Our main tool is an enhanced skeleton decomposition of the random PólyaA ntree with n leaves and no internal vertices having only one child. As a byproduct, we obtain limits describing the asymptotic shape of this model of random trees.