Premium
Graph limits of random graphs from a subset of connected k ‐trees
Author(s) -
Drmota Michael,
Jin Emma Yu,
Stufler Benedikt
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20802
Subject(s) - combinatorics , mathematics , random tree , random graph , tree (set theory) , discrete mathematics , graph , random regular graph , chordal graph , 1 planar graph , computer science , motion planning , artificial intelligence , robot
For any set Ω of non‐negative integers such that { 0 , 1 } ⊊ Ω , we consider a random Ω‐ k ‐tree G n , k that is uniformly selected from all connected k ‐trees of ( n + k ) vertices such that the number of ( k + 1)‐cliques that contain any fixed k ‐clique belongs to Ω. We prove that G n , k , scaled by ( k H k σ Ω ) / ( 2 n ) where H k is the k th harmonic number and σ Ω > 0, converges to the continuum random tree T e . Furthermore, we prove local convergence of the random Ω‐ k ‐treeG n , k ∘to an infinite but locally finite random Ω‐ k ‐tree G ∞, k .