Enumeration and randomized constructions of hypertrees. Issue 3 (15th January 2019)

• Record Type: Journal Article
• Authors: Linial, Nati; Peled, Yuval
• Is Part Of: Random structures & algorithms. Volume 55:Issue 3(2019)
• Page Start: 677
• Page End: 695
• Publication Date: 2019-01-15
• Subjects: Homology -- Hypertrees -- Simplicial Complexes -- The Probabilistic Method; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20841
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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.