Back to Search
Start Over
Graph limits of random graphs from a subset of connected $k$-trees
- 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
- Subjects :
- Mathematics - Probability
Mathematics - Combinatorics
60C05
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1605.05191
- Document Type :
- Working Paper