Graph limits of random graphs from a subset of connected k‐trees. Issue 1 (11th September 2018) - Drmota, Michael; Jin, Emma Yu; Stufler, Benedikt
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 .