liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The k-assignment Polytope and the Space of Evolutionary Trees
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, The Institute of Technology.
2004 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

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.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1117
Keyword [en]
k-assignment, polytope, Birkhoff polytope, bipartite graphs
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-5677Local ID: LiU-TEK-LIC-2004:46ISBN: 91-85295-45-0 (print)OAI: oai:DiVA.org:liu-5677DiVA: diva2:21437
Presentation
2004-10-26, 00:00 (English)
Supervisors
Available from: 2005-03-09 Created: 2005-03-09 Last updated: 2013-11-14Bibliographically approved
List of papers
1. The k-assignment polytope
Open this publication in new window or tab >>The k-assignment polytope
2009 (English)In: DISCRETE OPTIMIZATION, ISSN 1572-5286 , Vol. 6, no 2, 148-161 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we Study 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. A representation of the faces by certain bipartite graphs is given. This tool is used to describe the properties of the polytope, especially a complete description of the cover relation in the face poset of the polytope and an exact expression for the diameter. An ear decomposition of these bipartite graphs is constructed.

Keyword
Birkhoff polytope, Partial matching, Face poset, Ear decomposition, Assignment polytope
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-17621 (URN)10.1016/j.disopt.2008.10.003 (DOI)
Note
Original Publication: Jonna Gill and Svante Linusson, The k-assignment polytope, 2009, DISCRETE OPTIMIZATION, (6), 2, 148-161. http://dx.doi.org/10.1016/j.disopt.2008.10.003 Copyright: Elsevier Science B.V. Amsterdam http://www.elsevier.com/ Available from: 2009-04-30 Created: 2009-04-06 Last updated: 2013-11-14Bibliographically approved
2. A regular decomposition of the edge-product space of phylogenetic trees
Open this publication in new window or tab >>A regular decomposition of the edge-product space of phylogenetic trees
2008 (English)In: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 14, no 2, 158-176 p.Article in journal (Refereed) Published
Abstract [en]

We investigate the topology and combinatorics of a topological space called the edge-product space that is generated by the set of edge-weighted finite labelled trees. This space arises by multiplying the weights of edges on paths in trees, and is closely connected to tree-indexed Markov processes in molecular evolutionary biology. In particular, by considering combinatorial properties of the Tuffley poset of labelled forests, we show that the edge-product space has a regular cell decomposition with face poset equal to the Tuffley poset.

Keyword
Trees; Forests; Partitions; Poset; Regular cell complex; Recursive coatom ordering
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-18010 (URN)10.1016/j.aam.2006.07.007 (DOI)
Note
Original Publication: Jonna Gill, Svante Linusson, Vincent Moulton and Mike Steel, A regular decomposition of the edge-product space of phylogenetic trees, 2008, Advances in Applied Mathematics, (14), 2, 158-176. http://dx.doi.org/10.1016/j.aam.2006.07.007 Copyright: Elsevier Science B.V., Amsterdam http://www.elsevier.com/ Available from: 2009-04-30 Created: 2009-04-30 Last updated: 2017-12-13Bibliographically approved

Open Access in DiVA

fulltext(503 kB)812 downloads
File information
File name FULLTEXT01.pdfFile size 503 kBChecksum MD5
008be204bcf6efce32c7a2a1db3da874eac8205ef1116febfe840c2ba7fbc8b805a4bd55
Type fulltextMimetype application/pdf

Authority records BETA

Gill, Jonna

Search in DiVA

By author/editor
Gill, Jonna
By organisation
Applied MathematicsThe Institute of Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 812 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 582 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf