The asymptotic scarcity conjecture for collapsible hypertrees

Let Tn,d{\mathcal T_{n,d}} denote the family of nn-vertex dd-hypertrees, and let Cn,d{\mathcal C_{n,d}} denote the set of nn-vertex dd-collapsible dd-hypertrees. Here, a dd-collapsible dd-hypertree is a dd-hypertree that can be reduced by elementary dd-collapses, each removing an exposed (d1)(d-1)-face and its unique containing dd-face. Asymptotic scarcity conjecture. For every d2d\ge 2, asymptotically almost none of the dd-hypertrees are dd-collapsible; namely,

Cn,dTn,d0\frac{|{\mathcal C_{n,d}}|}{|{\mathcal T_{n,d}}|}\to 0

as nn\to\infty. This conjecture asserts that, despite collapsibility characterizing ordinary trees, dd-collapsible hypertrees form a vanishing fraction of all dd-hypertrees in every higher dimension.

Sources & referencesView supporting material

Primary source

Nati Linial and Yuval Peled, “Enumeration and randomized constructions of hypertrees”, arXiv:1801.02423 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.