M.Sc Thesis | |

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
*c _{d,k}*