Random Structures & Algorithms

Enumeration and randomized constructions of hypertrees

Early View

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.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.