|M.Sc Student||Tenenbaum Lior|
|Subject||Estimation of the Weighted Number of Simplicial Spanning|
Trees of Random K-Regular Simplicial Complexes
|Department||Department of Mathematics||Supervisor||ASSOCIATE PROF. Ron Rosenthal|
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.