The k-assignment Polytope and the Space of Evolutionary Trees
2004 (English)Licentiate thesis, comprehensive summary (Other academic)
This thesis consists of two papers.
The first paper is a study of the structure of the k-assignment polytope, whose vertices are the m x n (0; 1)-matrices with exactly k 1:s and at most one 1 in each row and each column. This is a natural generalisation of the Birkhoff polytope and many of the known properties of the Birkhoff polytope are generalised. Two equivalent representations of the faces are given, one as (0; 1)-matrices and one as ear decompositions of bipartite graphs. These tools are used to describe properties of the polytope, especially a complete description of the cover relation in the face lattice of the polytope and an exact expression for the diameter.
The second paper studies the edge-product space Є(X) for trees on X. This space is generated by the set of edge-weighted finite trees on X, and arises by multiplying the weights of edges on paths in trees. These spaces are closely connected to tree-indexed Markov processes in molecular evolutionary biology. It is known that Є(X) has a natural CW-complex structure, and a combinatorial description of the associated face poset exists which is a poset S(X) of X-forests. In this paper it is shown that the edge-product space is a regular cell complex. One important part in showing that is to conclude that all intervals [Ô, Г], Г Є S(X), have recursive coatom orderings.
Place, publisher, year, edition, pages
Matematiska institutionen , 2004. , 68 p.
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1117
k-assignment, polytope, Birkhoff polytope, bipartite graphs
IdentifiersURN: urn:nbn:se:liu:diva-5677Local ID: LiU-TEK-LIC-2004:46ISBN: 91-85295-45-0OAI: oai:DiVA.org:liu-5677DiVA: diva2:21437
2004-10-26, 00:00 (English)
List of papers