M.Sc Thesis


M.Sc StudentTenenbaum Lior
SubjectEstimation of the Weighted Number of Simplicial Spanning
Trees of Random K-Regular Simplicial Complexes
DepartmentDepartment of Mathematics
Supervisor ASSOCIATE PROF. Ron Rosenthal


Abstract

A spanning tree T of a graph G is a sub-graph of G with the same vertex set as G that is a tree, namely, a connected graph that does not contain loops. In 1981, McKay proved an asymptotic result regarding the number of spanning trees in a random k-regular graphs, sampled according to the matching model. His result is based on the fact that for any fixed natural number r, the ball of radius r around a uniformly sampled point in the graph is isomorphic to the ball of radius r in the k-regular tree with probability tending to 1 as n tends to infinity.

In this thesis we discuss analogue results for random high dimensional k-regular simplicial complexes, called Steiner complexes. First, we show that for any fixed natural number r, the high-dimensional ball of radius r around a typical co-dimension 1 cell in the complex is isomorphic to the ball of radius r in the k-regular arboreal complex of the appropriate dimension with probability that tends to 1 as the number of vertices tend to infinity, where the k-regular arboreal complex is a high-dimensional variant of the k-regular tree. Secondly, we use the first result in order to show that the weighted number of simplicial spanning trees in such complexes converges asymptotically to an explicit constant cd,k, when n tends to infinity, provided k is larger than a number depending only on the appropriate dimension.