Over thirty years ago, Kalai proved a beautiful d-dimensional analog of Cayley's formula for the number of
n-vertex trees. Namely, 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. We analyse a random-greedy construction of
d-hypertrees and show it significantly improves the previous known lower bound for their number. Second, we introduce a model of random 1-out d-dimensional complexes, and show that it has a negligible d-dimensional homology with high probability.
Joint work with Nati Linial
Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.
The ACO Seminar (2018–2019)