Please use this identifier to cite or link to this item: https://ah.nccu.edu.tw/handle/140.119/139047


Title: On the asymptotic growth of the number of tree-child networks
Authors: 符麥克
Fuchs, Michael
Yu, Guan-Ru
Zhang, Louxin
Contributors: 應數系
Date: 2021-03
Issue Date: 2022-02-10 14:59:42 (UTC+8)
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 where a1=-2.338107410... is the largest root of the Airy function of the 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.
Relation: European J. Combin., Vol.93, pp.103278
Data Type: article
DOI 連結: https://doi.org/10.1016/j.ejc.2020.103278
Appears in Collections:[應用數學系] 期刊論文

Files in This Item:

File Description SizeFormat
359.pdf535KbAdobe PDF25View/Open


All items in 學術集成 are protected by copyright, with all rights reserved.


社群 sharing