Back to Search Start Over

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

Authors :
Drmota, Michael
Jin, Emma Yu
Stufler, Benedikt
Publication Year :
2016

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 ${\sf 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 ${\sf G}_{n,k}$, scaled by $(kH_{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}_{{\sf e}}$. Furthermore, we prove the local convergence of the rooted random $\Omega$-$k$-tree ${\sf G}_{n,k}^{\circ}$ to an infinite but locally finite random $\Omega$-$k$-tree ${\sf G}_{\infty,k}$.<br />Comment: 21 pages, 6 figures

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1605.05191
Document Type :
Working Paper