Simplicial spanning trees in random Steiner complexes

DOI10.1007/S00493-023-00038-3MaRDI QIDQ6081386zbMATH OpenOpenAlexFDO

Authors Ron Rosenthal, Lior Tenenbaum

Publication date 4 October 2023

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.06955

zbMATH Keywords

Benjamini-Schramm convergenceKesten-McKay distributionrandom simplicial complexesrandom Steiner systemssimplicial spanning trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial aspects of simplicial complexes (05E45) Probability theory on algebraic and topological structures (60B99) Combinatorial probability (60C05)

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 $$ as $noinfty$, where $x{i}_{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.

Recommendations

• On the number of spanning trees in random regular graphs
• Spanning trees in random regular uniform hypergraphs
• Asymptotic Enumeration of Spanning Trees
• Simplicial matrix-tree theorems
• Spanning trees in random graphs

Cited in

(2)

• Simplex links in determinantal hypertrees
• Eigenvalues and spectral gap in sparse random simplicial complexes

This page was built for publication: Simplicial spanning trees in random Steiner complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081386)