The generator-count asymptotic conjecture for random tanglegrams

Let BnB_n denote the set of binary trees with nn leaves. For a binary tree TT, let l(T)l(T) be its number of leaves and k(T)k(T) its number of symmetries, meaning vertices with identical subtrees. Let TBnT'\in B_n be the left tree of a uniformly random tanglegram, and let A(T)A(T') be the associated object whose generators are being counted. Generator-count conjecture. The expected number of generators of A(T)A(T') is asymptotically equal to

(TBn14l(T)+k(T))n.\left(\sum_{T\in B_n}\frac{1}{4^{l(T)+k(T)}}\right)n.

The claim is presented as a consequence that would follow if the preceding subtree-count conjectures hold; the source does not establish it.

Sources & referencesView supporting material

Primary source

Sara Billey, Matjaž Konvalinka and Frederick A Matsen, “On the enumeration of tanglegrams and tangled chains”, arXiv:1507.04976 (2015).

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.