Random cographs: Brownian graphon limit and asymptotic degree distribution
From MaRDI portal
(Redirected from Publication:6074680)
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 , and converges after normalization to the Lebesgue measure on . 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
Cites work
- A decorated tree approach to random permutations in substitution-closed classes
- A Linear Recognition Algorithm for Cographs
- A simple linear time algorithm for cograph recognition
- A Simple Linear Time LexBFS Cograph Recognition Algorithm
- 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
- 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?)
- 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 graphs from subcritical classes
- Scaling limits of random Pólya trees
- 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
(10)- 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
- The permuton limit of random recursive separable permutations
- A canonical tree decomposition for chirotopes
- A canonical tree decomposition for order types, and some applications
- Scaling limit of graph classes through split decomposition
- On the edge-density of the Brownian co-graphon and common ancestors of pairs in the CRT
- Subgraph densities and scaling limits of random graphs with a prescribed modular decomposition
- Graph classes with few P₄'s: universality and Brownian graphon limits
- Dense and nondense limits for uniform random intersection graphs
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)
