论文标题
关于树木网络数量的渐近生长
On the Asymptotic Growth of the Number of Tree-Child Networks
论文作者
论文摘要
在最近的一篇论文中，McDiarmid，Semple和Welsh（2015）表明，具有$ N $叶子的树木网络的数量在其主要的渐近增长期限为$ n^{2n} $。在本文中，我们通过将主要渐近生长项完全识别为常数来改善这一点。更准确地说，我们表明，带有$ n $叶子的树木网络数量如\ [θ\ left（n^{ - 2/3} $ a_1 = -2.338107410 \ cdots $是第一类通风函数的最大根。为了证明，我们将基本的图理论问题纵容地映射到单词上的问题上。对于后者，我们可以找到一种重复发生的，可以应用一种最近强大的Elvey Price，Fang和Wallner（2019）的复发。
In a recent paper, McDiarmid, Semple, and Welsh (2015) showed that the number of tree-child networks with $n$ leaves has the factor $n^{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 $n$ leaves grows like \[ Θ\left(n^{-2/3}e^{a_1(3n)^{1/3}}\left(\frac{12}{e^2}\right)^{n}n^{2n}\right), \] where $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.
