Date of Award

2015

Document Type

Open Access Dissertation

Department

Mathematics

Sub-Department

College of Arts and Sciences

First Advisor

László A. Székely

Abstract

This dissertation contains work on three main topics.

Chapters 1 through 4 provide complexity results for the single cut-or-join model for genome rearrangement. Genomes will be represented by binary strings. Let S be a finite collection of binary strings, each of the same length. Define M to be the collection of medians – binary strings μ which minimize Sigma v belongs to S H(μ,v) where H is the Hamming distance. For any non-negative function f(x), define Z(f(x), S) to be (Sigma μ belongs to M) (Pi v belongs to S)f(H(μ,v)). We study the complexity of calculating Z(f(x), S), with respect to the number of strings in S and their length.

If the leaves of a star are labeled with the strings in S, then Z(x!, S) counts the pairs of functions where one selects a median μ for S and the other assigns, to each v belongs to S, a permutation of coordinates in which μ and v differ. This relates to the small parsimony problem for genome rearrangement. We show that it is #P-complete to calculate Z(x!, S) and give similar results for other functions f(x). We also consider an analogous problem when the leaves of a binary tree are labeled. This is joint work with István Miklós.

Chapters 5 and 6 explore tree invariants. In particular, Chapter 5 examines the eccentricity of a vertex, eccT (v) = maxu2T dT (v, u) where dT (u, v) is the number of edges along the path connecting u and v in T. This was one of the first, distancebased, tree invariants studied (Jordan 1869). The total eccentricity of a tree, Ecc(T), is the sum of the eccentricities of its vertices. We determine extremal values and characterize extremal tree structures for the ratios Ecc(T)/ eccT (u), Ecc(T)/ eccT (v), eccT (u)/ eccT (v), and eccT (u)/ eccT (w) where u,w are leaves of T and v is in the center of T. Analogous problems have been resolved for other tree invariants including distance (Barefoot, Entringer, and Székely 1997) and the number of subtrees (Székely and Wang 2013). In addition, we determine the tree structures that minimize and maximize total eccentricity among trees with a given degree sequence. This is joint work with László Székely and Hua Wang.

Chapter 6 compares three different middle parts of a tree. Different middle parts such as center, centroid, subtree core have been defined and studied. We want to provide some general insights on the difference between them and consider how far apart (with given order of the tree) two different ‘middle point’ can be and when such maximum distances are achieved. This study, after conducted on general trees, is naturally extended to trees with restricted degrees or diameter due to the evident correlation between these restrictions and the maximum distance between middle parts. Some related interesting questions arise that may be of interest independently. This is joint work with László Székely, Hua Wang, and Shuai Yuan.

Chapter 7 studies a problem related to Baranyai’s Theorem. This guarantees that whenever k divides n, there is a partition of ([n]Ck) into rows such that each row is itself a partition of [n]. Baranyai (1973) used graph flows to give an existence proof for this 118 year old conjecture. We are interested in the structure of these partitions. For k = 2, there is a circular configuration which yields a straightforward construction. Beth (1974) found an algebraic construction for k = 3. However neither method has a known extension to larger k. We consider a new construction for k = 2 which makes use of a bijection between partitions and labeled trees. It is our hope that this type of connection will lead to a more general construction of Baranyai partitions. This is joint work with László Székely.

Rights

© 2015, Heather Christina Smith

Download

Included in

Mathematics Commons

Share

COinS