Premium
Enumeration and randomized constructions of hypertrees
Author(s) -
Linial Nati,
Peled Yuval
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20841
Subject(s) - enumeration , vertex (graph theory) , homology (biology) , combinatorics , mathematics , face (sociological concept) , upper and lower bounds , discrete mathematics , biology , genetics , graph , mathematical analysis , gene , social science , sociology
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.