Random cographs: Brownian graphon limit and asymptotic degree distribution

DOI10.1002/RSA.21033zbMATH Open1526.05123arXiv1907.08517OpenAlexW3180425134MaRDI QIDQ6074680FDOQ6074680

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)

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.

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

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

zbMATH Keywords

cographsdegree distributionBrownian excursiongraphons

Mathematics Subject Classification ID

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

Cites Work

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

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)