On the asymptotic growth of the number of tree-child networks

DOI10.1016/J.EJC.2020.103278MaRDI QIDQ2225459zbMATH OpenOpenAlexFDO

Authors Michael Fuchs, G.-R. Yu, Louxin Zhang

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.08049

zbMATH Keywords

phylogenetic networkstree-child networksasymptotic growth

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Problems related to evolution (92D15) Systems biology, networks (92C42)

Abstract: 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 [ Thetaleft(n^{-2/3}e^{a_1(3n)^{1/3}}left(frac{12}{e^2} ight)^{n}n^{2n} ight), ] where $a_1=-2.338107410cdots$ 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.

Recommendations

• Counting phylogenetic networks with few reticulation vertices: a second approach
• Counting phylogenetic networks
• Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks
• Counting general phylogenetic networks
• Asymptotic enumeration and distributional properties of galled networks

Cites work

• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• Compacted binary trees admit a stretched exponential
• Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks
• Counting and enumerating galled networks
• Counting and enumerating tree-child networks and their subclasses
• Counting phylogenetic networks

Cited in

(13)

• Combinatorial and stochastic properties of ranked tree‐child networks
• Counting phylogenetic networks with few reticulation vertices: galled and reticulation-visible networks
• Limit theorems for patterns in ranked tree‐child networks
• Labellable phylogenetic networks
• Counting phylogenetic networks with few reticulation vertices: a second approach
• Bijections for ranked tree-child networks
• Generation of orchard and tree-child networks
• The Sackin index of simplex networks
• Combinatorics arising from lax colimits of posets
• Young tableaux with periodic walls: counting with the density method
• Enumerative and distributional results for \(d\)-combining tree-child networks
• Asymptotic enumeration and distributional properties of galled networks
• Bounding the number of reticulations in a tree-child network that displays a set of trees

This page was built for publication: On the asymptotic growth of the number of tree-child networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225459)