On the Asymptotic Growth of the Number of Tree-Child Networks

preprint2020arXivOpen access

Abstract

In a recent paper, McDiarmid, Semple, and Welsh (2015) showed that the number of tree-child networks with nn leaves has the factor n2nn^{2n} in its main asymptotic growth term. In this paper, we improve this by completely identifying the main asymptotic growth term up to a constant. More precisely, we show that the number of tree-child networks with nn leaves grows like Θ(n−2/3ea1(3n)1/3(12e2)nn2n), Θ\left(n^{-2/3}e^{a_1(3n)^{1/3}}\left(\frac{12}{e^2}\right)^{n}n^{2n}\right), where a1=−2.338107410⋯a_1=-2.338107410\cdots is the largest root of the Airy function of first kind. For the proof, we bijectively map the underlying graph-theoretical problem onto a problem on words. For the latter, we can find a recurrence to which a recent powerful asymptotic method of Elvey Price, Fang, and Wallner (2019) can be applied.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.