Random cographs: Brownian graphon limit and asymptotic degree distribution

DOI10.1002/RSA.21033MaRDI QIDQ6074680zbMATH OpenOpenAlexFDO

Authors Frédérique Bassino, Mathilde Bouvel, Valentin Féray, L. Gerin, Mickaël Maazoun, Adeline Pierrot

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.08517

zbMATH Keywords

cographsdegree distributionBrownian excursiongraphons

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07)

Abstract: We consider uniform random cographs (either labeled or unlabeled) of large size. Our first main result is the convergence towards 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 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.

Recommendations

• Graphon convergence of random cographs
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Asymptotic properties of random unlabelled block-weighted graphs
• Limits of random trees. II

Cites work

• scientific article; zbMATH DE number 5130821 (Why is no real title available?)
• scientific article; zbMATH DE number 563055 (Why is no real title available?)
• scientific article; zbMATH DE number 758277 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• A decorated tree approach to random permutations in substitution-closed classes
• A simple linear time algorithm for cograph recognition
• Analytic combinatorics
• Asymptotic for the cumulative distribution function of the degrees and homomorphism densities for random graphs sampled from a graphon
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Complement reducible graphs
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Full asymptotic expansion for Pólya structures
• Fundamentals of Stein's method
• Graph limits and exchangeable random graphs
• Graph limits and hereditary properties
• Graph properties, graph limits, and entropy
• Graphon convergence of random cographs
• Large networks and graph limits
• Measure theory. Vol. I and II
• On a property of the class of n-colorable graphs
• On the Brownian separable permuton
• On the shape of random Pólya structures
• Random measures, theory and applications
• Random perfect graphs
• Random planar graphs and beyond
• Random trees and applications
• Scaling limits of random Pólya trees
• Scaling limits of random graphs from subcritical classes
• Some families of trees arising in permutation analysis
• The Brownian limit of separable permutations
• The evolution of random graphs on surfaces
• The method of moments and degree distributions for network models
• Threshold graph limits and random threshold graphs
• Universal limits of substitution-closed permutation classes

Cited in

(3)

• The permuton limit of random recursive separable permutations
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons

This page was built for publication: Random cographs: Brownian graphon limit and asymptotic degree distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074680)