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, phylogenetic trees, and permutation patterns
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, The Institute of Technology.
2013 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis three combinatorial problems are studied in four papers.

In Paper 1 we study the structure of the k-assignment polytope, whose vertices are the mxn (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 representation is used to describe the properties of the polytope, such as a complete description of the cover relation in the face poset of the polytope and an exact expression for the diameter of its graph. An ear decomposition of these bipartite graphs is constructed.

In Paper 2 we investigate the topology and combinatorics of a topological space, called the edge-product space, that is generated by a set of edge-weighted finite semi-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 semi-labelled forests, we show that the edge-product space has a regular cell decomposition with face poset equal to the Tuffley poset. 

The elements of the Tuffley poset are called X-forests, where X is a finite set of labels. A generating function of the X-forests withrespect to natural statistics is studied in Paper 3 and a closed formula is found. In addition, a closed formula for the corresponding generating function of X-trees is found. Singularity analysis is used on these formulas to find asymptotics for the number of components, edges, and unlabelled nodes in X-forests and X-trees as |X| goes towards infinity.

In Paper 4 permutation statistics counting occurrences of patterns are studied. Their expected values on a product of t permutations chosen randomly from a subset Γ of Sn, where Γ is a union of conjugacy classes, are considered. Hultman has described a method for computing such an expected value, denoted E(s,t), of a statistic s, when Γ is a union of conjugacy classes of Sn. The only prerequisite is that the mean of s over the conjugacy classes is written as a linear combination of irreducible characters of Sn. Therefore, the main focus of this paper is to express the means of pattern-counting statistics as such linear combinations. A procedure for calculating such expressions for statistics counting occurrences of classical and vincular patterns of length 3 is developed, and is then used to calculate all these expressions.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2013. , 21 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1544
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-98263DOI: 10.3384/diss.diva-98263ISBN: 978-91-7519-510-0 (print)OAI: oai:DiVA.org:liu-98263DiVA: diva2:653747
Public defence
2013-12-17, Nobel, B-huset, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Supervisors
Available from: 2013-11-14 Created: 2013-10-05 Last updated: 2013-11-25Bibliographically 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, 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: 2013-11-14Bibliographically approved
3. A generating function for X-forests
Open this publication in new window or tab >>A generating function for X-forests
(English)Manuscript (preprint) (Other academic)
Abstract [en]

The Tuffley poset is a poset of a certain kind of semi-labelled forests called X-forests, where X is a finite set of labels. This poset is closely related to a topological space of phylogenetic trees called the edgeproduct space. A generating function of the elements in the Tuffley poset with respect to natural statistics is studied and a closed formula is found. In addition, a closed formula for the corresponding generating function of X-trees is found. Singularity analysis is used on these formulas to find asymptotics for the number of components, edges, and unlabelled nodes in X-forests and X-trees as |X| → ∞.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-100892 (URN)
Available from: 2013-11-14 Created: 2013-11-14 Last updated: 2013-11-14Bibliographically approved
4. Pattern containment in random permutations
Open this publication in new window or tab >>Pattern containment in random permutations
(English)Manuscript (preprint) (Other academic)
Abstract [en]

This paper studies permutation statistics that count occurrences of patterns. Their expected values on a product of t permutations chosen randomly from Γ  Sn, where G is a union of conjugacy classes, are considered. Hultman has described a method for computing such an expected value, denoted EΓ(s, t), of a statistic s, when Γ is a union of conjugacy classes of Sn. The only prerequisite is that the mean of s over the conjugacy classes is written as a linear combination of irreducible characters of Sn. Therefore, the main focus of this article is to express the means of pattern-counting statistics as such linear combinations. A procedure for calculating such expressions for statistics counting occurrences of classical and vincular patterns of length 3 is developed, and is then used to calculate all these expressions. The results can be used to compute EΓ(s, t) for all the above statistics, and for all functions on Sn that are linear combinations of them.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-100894 (URN)
Available from: 2013-11-14 Created: 2013-11-14 Last updated: 2013-11-14Bibliographically approved

Open Access in DiVA

The k-assignment polytope, phylogenetic trees, and permutation patterns(183 kB)369 downloads
File information
File name FULLTEXT02.pdfFile size 183 kBChecksum SHA-512
cfaa25caa28fa252ba0b3c480408c5546de1722b5a98057f68b7e84a4c7c5167ef3388fd5ad2ce9301b0195d529a3005b46bb131263229807b750f26b9c0b9ac
Type fulltextMimetype application/pdf
omslag(89 kB)31 downloads
File information
File name COVER01.pdfFile size 89 kBChecksum SHA-512
8801ff188e967b45f770bc9fe475c76c8774de0fa506304fe83a973fe0d8f0484223afbc7943c1eb24b5e8b82264722d47c1b4febd1ea2222aba8a727af79c81
Type coverMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Gill, Jonna

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 369 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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 1415 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