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

Abstract

For any set $\Omega$ of non-negative integers such that $\{0,1\}\subseteq \Omega$ and $\{0,1\}\ne \Omega$, we consider a random $\Omega$-$k$-tree ${\mathsf{G}}_{n,k}$ that is uniformly selected from all connected $k$-trees of $(n+k)$ vertices where the number of $(k+1)$-cliques that contain any fixed $k$-clique belongs to $\Omega$. We prove that ${\mathsf{G}}_{n,k}$, scaled by $(k{H}_k{\sigma }_{\Omega })/(2\sqrt{n})$ where $H_k$ is the $k$-th Harmonic number and ${\sigma }_{\Omega }>0$, converges to the Continuum Random Tree ${\mathcal{T}}_{\mathsf{e}}$. Furthermore, we prove the local convergence of the rooted random $\Omega$-$k$-tree ${\mathsf{G}}_{n,k}^{\circ }$ to an infinite but locally finite random $\Omega$-$k$-tree ${\mathsf{G}}_{\infty ,k}$.

arXiv comment21 pages, 6 figures