ACO The ACO Seminar (2018–2019)

November 29, 3:30pm, Wean 8220
Yuval Peled, Courant Institute
Enumeration and randomized constructions of hypertrees


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.

Back to the ACO home page