Graphon convergence of random cographs. Issue 3 (28th February 2021)

• Record Type: Journal Article
• Authors: Stufler, Benedikt
• Is Part Of: Random structures & algorithms. Volume 59:Issue 3(2021)
• Page Start: 464
• Page End: 491
• Publication Date: 2021-02-28
• Subjects: cographs -- distributional limits -- graphons; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21002
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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ólya A n tree 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.