| 1. |
- Gill, Jonna
(författare)
-
A generating function for X-forests
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- 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| → ∞.
|
|
| 2. |
- Gill, Jonna, et al.
(författare)
-
A regular decomposition of the edge-product space of phylogenetic trees
- 2008
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 41:2, s. 158-176
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 3. |
- Gill, Jonna
(författare)
-
Pattern containment in random permutations
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 4. |
- Gill, Jonna, et al.
(författare)
-
The k-assignment polytope
- 2009
-
Ingår i: DISCRETE OPTIMIZATION. - : Elsevier BV. - 1572-5286. ; 6:2, s. 148-161
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 5. |
- Gill, Jonna, 1979-
(författare)
-
The k-assignment Polytope and the Space of Evolutionary Trees
- 2004
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 6. |
- Gill, Jonna, 1979-
(författare)
-
The k-assignment polytope, phylogenetic trees, and permutation patterns
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
