Enumeration Results On Leaf Labeled Trees

<p>ENUMERATION RESULTS ON LEAF LABELED TREES,Virginia P. Johnson In evolutionary biology, it is common practice to represent the evolution of species, populations, and organisms with graphs, called phylogenetic or species trees. These are rooted leaf-labeled trees where non-root internal vertices have degree at least three and each label is used once. Multi-labeled trees are a generalization of phylogenetic trees that are used in the study of gene versus species evolution and as the basis for phylogenetic network construction. Unlike phylogenetic trees, in a leaf-multi-labeled tree it is possible to label more than one leaf by the same element of the underlying label set. In this thesis we first derive formulae for generating functions of leaf-multi-labeled trees and use these to derive recursions for counting such trees. In particular, we prove results which generalize previous theorems by Harding on so-called tree-shapes, and by Otter on relating the number of rooted and unrooted phylogenetic trees. Turning our attention to phylogenetic or species trees we show the asymtotic normality of categories of phylogenetic trees. P.L. Erdos and L.A. Szekely [Adv. Appl. Math.series 10,1989, 488--496] gave a bijection between rooted semilabeled trees and set partitions. L.H. Harper's results [Ann. Math.Stat.series 38, 1967, 410--414] on the asymptotic normality of the Stirling numbers of the second kind translates into asymptotic normality of rooted semilabeled trees with given number of vertices, when the number of internal vertices varies. The Erdos-Szekely bijection specializes to a bijection between phylogenetic trees and set partitions with classes of size at least 2. We consider modified Stirling numbers of the second kind that enumerate partitions of a fixed set into a given number of classes of size $\geq 2$, and obtain their asymptotic normality as the number of classes varies.The Erdos-Szekely bijection translates this result into the asymptotic normality of the number of phylogenetic trees with given number of vertices, when the number of leaves varies. We also obtain asymptotic normality of the number of phylogenetic trees with given number of leaves and varying number of internal vertices, which make more sense to students of phylogeny. This is accomplished by showing the asymptotic normality of the numberof partitions of $n+m$ elements into $m$ classes of size $\geq 2$, when $n$ is fixed and $m$ varies, which with the Erdos-Szekely bijection gives the result we want.The proofs are adaptations of the techniques of L.H. Harper [Ibid.].</p>

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Campus Access Dissertation

Discipline thesis:degree_discipline

Mathematics

Year

2012

Author dc:creator

• Johnson, Virginia Perkins

Contributors dc:contributor

• Eva Czabarka

• Mathematics
• Physical Sciences and Mathematics
• asymptotic enumeration
• generating function
• MUL_trees
• Otter's Theorem
• phylogenetc trees
• set partition

Statement dc:rights

• © 2012, Virginia Perkins Johnson

Repository record dc:identifier

https://scholarcommons.sc.edu/etd/1601

OAI identifier oai:identifier

oai:scholarcommons.sc.edu:etd-2602