Enumeration and randomized constructions of hypertrees
Nati Linial, Yuval Peled · Random Structures and Algorithms · 2019
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.