Enumeration and randomized constructions of hypertrees
Enumeration and randomized constructions of hypertrees
复制标题
超树的枚举和随机构造
DOI：
10.1002/rsa.20841
复制
发表时间：
2018
影响因子：
1
通讯作者：
Y. Peled
中科院分区：
文献类型：
--
作者：
N. Linial;Y. Peled
30多年前，Kalai证明了一个漂亮的d维类似于Cayley的n顶点树的数量公式。他列举了d维超树，这些超树由它们的（d − 1）维同调群的平方大小加权。然而，这并没有回答更基本的d-超树的未加权枚举问题，这是我们在这里关注的问题。我们的主要结果，定理1.4，显著地改进了d-超树个数的下界。此外，我们研究了d-复形的随机1-out模型，其中每个（d-1）维面选择一个包含它的随机d-面，并证明它具有可忽略的d-维同调。
Over 30 years ago, Kalai proved a beautiful d‐dimensional analog of Cayley's formula for the number of n‐vertex trees. He enumerated d‐dimensional hypertrees weighted by the squared size of their (d − 1)‐dimensional homology group. This, however, does not answer the more basic problem of unweighted enumeration of d‐hypertrees, which is our concern here. Our main result, Theorem 1.4, significantly improves the lower bound for the number of d‐hypertrees. In addition, we study a random 1‐out model of d‐complexes where every (d − 1)‐dimensional face selects a random d‐face containing it, and show that it has a negligible d‐dimensional homology.