<p>This thesis consists of two papers.</p><p>The first paper is a study of the structure of the k-assignment polytope, whose vertices are the <em>m x n</em> (0; 1)-matrices with exactly <em>k</em> 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.</p><p>The second paper studies the edge-product space <em>Є(X)</em> for trees on <em>X</em>. This space is generated by the set of edge-weighted finite trees on <em>X</em>, 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 <em>Є(X)</em> has a natural <em>CW</em>-complex structure, and a combinatorial description of the associated face poset exists which is a poset <em>S(X)</em> of <em>X</em>-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 <em>[Ô, Г], Г </em>Є<em> S(X),</em> have recursive coatom orderings.</p> / Report code: LiU-TEK-LIC-2004:46.
| Identifer | oai:union.ndltd.org:UPSALLA/oai:DiVA.org:liu-5677 |
| Date | January 2004 |
| Creators | Gill, Jonna |
| Publisher | Linköping University, Linköping University, Applied Mathematics, Matematiska institutionen |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Licentiate thesis, monograph, text |
| Relation | Linköping Studies in Science and Technology. Thesis, 0280-7971 ; 1117 |
Page generated in 0.002 seconds