Graph limits of random graphs from a subset of connected k-trees

Abstract

For any set Ω of non-negative integers such that urn:x-wiley:rsa:media:rsa20802:rsa20802-math-0001, we consider a random Ω-k-tree Gn,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 Gn,k, scaled by urn:x-wiley:rsa:media:rsa20802:rsa20802-math-0002 where Hk is the kth harmonic number and σΩ > 0, converges to the continuum random tree urn:x-wiley:rsa:media:rsa20802:rsa20802-math-0003. Furthermore, we prove local convergence of the random Ω-k-tree urn:x-wiley:rsa:media:rsa20802:rsa20802-math-0004 to an infinite but locally finite random Ω-k-tree G∞,k.