[Zurück]

E. Jin:
"Graph limits of random graphs from a subset of connected k-trees";
Vortrag: Joint Conference of Austrian, Czech, Slovak, Slovenian and Catalonian Mathematical Societies, Barcelona; 20.09.2016 - 23.09.2016.

For any set $\Omega$ of non-negative integers which contains $0,1$ and at least one integer greater than $1$, we consider a random $\Omega$-$k$-tree ${\sf G}_{n,k}$ that is uniformly selected from the class of connected $k$-trees of $(n+k)$ vertices such that the number of $(k+1)$-cliques that contain any fixed $k$-clique belongs to the set $\Omega$.




We establish the scaling limit and a local weak limit of this random $\Omega$-$k$-tree ${\sf G}_{n,k}$. Since $1$-trees are just trees, it is well-known that the random $1$-tree with $n$ vertices admits the Continuum Random Tree $\CMcal{T}_{{\sf e}}$ as the scaling limit and converges locally toward a modified Galton-Watson tree. We prove that the random $\Omega$-$k$-tree ${\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}$ is a positive constant, converges to the Continuum Random Tree $\CMcal{T}_{{\sf e}}$, too. In particular this shows that the diameter as well as the expected distance of two vertices in a random $\Omega$-$k$-tree ${\sf G}_{n,k}$ are of order $\sqrt n$. Furthermore, we prove the local convergence of the random $\Omega$-$k$-tree ${\sf G}_{n,k}$ to an infinite but locally finite random $\Omega$-$k$-tree ${\sf G}_{\infty,k}$.

k-trees, partial k-trees, Continuum Random Tree, modified Galton-Watson tree