Graph limits of random graphs from a subset of connected k‐trees. Issue 1 (11th September 2018)

• Record Type: Journal Article
• Authors: Drmota, Michael; Jin, Emma Yu; Stufler, Benedikt
• Is Part Of: Random structures & algorithms. Volume 55:Issue 1(2019)
• Page Start: 125
• Page End: 152
• Publication Date: 2018-09-11
• Subjects: continuum random tree -- modified Galton‐Watson tree -- partial k‐trees; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20802
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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 ‐tree G n, k ∘ to an infinite but locally finite random Ω‐ k ‐tree G∞, k .