Enumeration and randomized constructions of hypertrees

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 unweig...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2019-10, Vol.55 (3), p.677-695
Main Authors: Linial, Nati, Peled, Yuval
Format: Article
Language:English
Subjects:
Enumeration
Homology
Hypertrees
Lower bounds
Simplicial Complexes
The Probabilistic Method
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.20841