Scaling limit of graph classes through split decomposition

2022/07/25 by Bassino, Frédérique, Bouvel, Mathilde, Féray, Valentin +2
#05A16 #05C80 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2207.12253

Abstract

We prove that Aldous' Brownian CRT is the scaling limit, with respect to the Gromov--Prokhorov topology, of uniform random graphs in each of the three following families of graphs: distance-hereditary graphs, 2-connected distance-hereditary graphs and 3-leaf power graphs. Our approach is based on the split decomposition and on analytic combinatorics.

Related

• The GHP scaling limit of uniform spanning trees of dense graphs
• The CRT is the scaling limit of unordered binary trees
• The GHP scaling limit of uniform spanning trees in high dimensions
• Subgraph densities and scaling limits of random graphs with a prescribed modular decomposition
• Scaling Limits of Random Graphs from Subcritical Classes