Simplicial spanning trees in random Steiner complexes

Abstract

A spanning tree $T$ in a graph $G$ is a sub-graph of $G$ with the same vertex set as $G$ which is a tree. In 1981, McKay proved an asymptotic result regarding the number of spanning trees in random $k$-regular graphs. In this paper we prove a high-dimensional generalization of McKay's result for random $d$-dimensional, $k$-regular simplicial complexes on $n$ vertices, showing that the weighted number of simplicial spanning trees is of order $({\xi }_{d,k}+o(1){)}^{\left(\genfrac{}{}{0ex}{}{n}{d}\right)}$ as $n\to \infty$, where ${\xi }_{d,k}$ is an explicit constant, provided $k>4d^2+d+2$. A key ingredient in our proof is the local convergence of such random complexes to the $d$-dimensional, $k$-regular arboreal complex, which allows us to generalize McKay's result regarding the Kesten-McKay distribution.

arXiv comment26 pages, 2 figures