Search Results

Documents authored by Agranat-Tamir, Lily

Document
DOI: 10.4230/LIPIcs.AofA.2024.27
Asymptotic Enumeration of Rooted Binary Unlabeled Galled Trees with a Fixed Number of Galls

Authors: Lily Agranat-Tamir, Michael Fuchs, Bernhard Gittenberger, and Noah A. Rosenberg

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
Galled trees appear in problems concerning admixture, horizontal gene transfer, hybridization, and recombination. Building on a recursive enumerative construction, we study the asymptotic behavior of the number of rooted binary unlabeled (normal) galled trees as the number of leaves n increases, maintaining a fixed number of galls g. We find that the exponential growth with n of the number of rooted binary unlabeled normal galled trees with g galls has the same value irrespective of the value of g ≥ 0. The subexponential growth, however, depends on g; it follows c_g n^{2g-3/2}, where c_g is a constant dependent on g. Although for each g, the exponential growth is approximately 2.4833ⁿ, summing across all g, the exponential growth is instead approximated by the much larger 4.8230ⁿ.
Cite as

Lily Agranat-Tamir, Michael Fuchs, Bernhard Gittenberger, and Noah A. Rosenberg. Asymptotic Enumeration of Rooted Binary Unlabeled Galled Trees with a Fixed Number of Galls. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{agranattamir_et_al:LIPIcs.AofA.2024.27,
  author =	{Agranat-Tamir, Lily and Fuchs, Michael and Gittenberger, Bernhard and Rosenberg, Noah A.},
  title =	{{Asymptotic Enumeration of Rooted Binary Unlabeled Galled Trees with a Fixed Number of Galls}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.27},
  URN =		{urn:nbn:de:0030-drops-204626},
  doi =		{10.4230/LIPIcs.AofA.2024.27},
  annote =	{Keywords: galled trees, generating functions, phylogenetics, unlabeled trees}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact