| 31. |
- Eriksson, K., et al.
(författare)
-
A combinatorial theory of higher-dimensional permutation arrays
- 2000
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 25:2, s. 194-211
-
Tidskriftsartikel (refereegranskat)abstract
- We define a class of hypercubic (shape [n](d)) arrays that in a certain sense are d-dimensional analogs of permutation matrices with our motivation from algebraic geometry. Various characterizations of permutation arrays are proved. an efficient generation algorithm is given, and enumerative questions are discussed although not settled. There is a partial order on the permutation arrays, specializing to the Bruhat order on S-n, when d equals 2, and specializing to the lattice of partitions of a d-set when n equals 2.
|
|
| 32. |
- Eriksson, K., et al.
(författare)
-
A decomposition of Fl(n)(d) indexed by permutation arrays
- 2000
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 25:2, s. 212-227
-
Tidskriftsartikel (refereegranskat)abstract
- We study a decomposition of Fl(n)(d-1), where: Fl(n) denotes the flag manifold over C-n. The strata are defined by the dimensions of intersections of one space from each fag, so for d equal to 2 this is the usual Bruhat cell decomposition, The strata are indexed by permutation arrays, which are d-dimensional analogs of permutation matrices. We present a partial order on these permutation arrays, specializing: to the Bruhat order on S-n when d equals 2 and to the lattice of partitions of a d-set when n equals 2.
|
|
| 33. |
- 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.
|
|
| 34. |
- 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.
|
|
| 35. |
- 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.
|
|
| 36. |
- Guibert, O., et al.
(författare)
-
Doubly alternating Baxter permutations are Catalan
- 2000
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 217:03-jan, s. 157-166
-
Tidskriftsartikel (refereegranskat)abstract
- The Baxter permutations who are alternating and whose inverse is also alternating are shown to be enumerated by the Catalan numbers. A bijection to complete binary trees is also given.
|
|
| 37. |
- Hopkins, Sam, et al.
(författare)
-
On the q-enumeration of barely set-valued tableaux and plane partitions
- 2023
-
Ingår i: European journal of combinatorics (Print). - : Elsevier BV. - 0195-6698 .- 1095-9971. ; 113
-
Tidskriftsartikel (refereegranskat)abstract
- Barely set-valued tableaux are a variant of Young tableaux in which one box contains two numbers as its entry. It has recently been discovered that there are product formulas enumerating certain classes of barely set-valued tableaux. We give some q-analogs of these product formulas by introducing a version of major index for these tableaux. We also give product formulas and q-analogs for barely set-valued plane partitions. Many of the results are stated in the generality of P-partitions that then specialize to particularly nice formulas for rectangles and minuscule posets. The proofs use several probability distributions on the set of order ideals of a poset, depending on the real parameter q>0, which we think could be of independent interest.
|
|
| 38. |
- Hultman, Axel, et al.
(författare)
-
From Bruhat intervals to intersection lattices and a conjecture of Postnikov
- 2008
-
Ingår i: FPSAC - Int. Conf. Form. Power Ser. Algebraic Comb.. ; , s. 203-214
-
Konferensbidrag (refereegranskat)abstract
- We prove the conjecture of A. Postnikov that (A) the number of regions in the inversion hyperplane arrangement associated with a permutation w ∈ S n is at most the number of elements below w in the Bruhat order, and (B) that equality holds if and only if w avoids the patterns 4231, 35142, 42513 and 351624. Furthermore, assertion (A) is extended to all finite reflection groups.
|
|
| 39. |
- Hultman, Axel, et al.
(författare)
-
From Bruhat intervals to intersection lattices and a conjecture of Postnikov
- 2009
-
Ingår i: Journal of combinatorial theory. Series A (Print). - : Elsevier BV. - 0097-3165 .- 1096-0899. ; 116:3, s. 564-580
-
Tidskriftsartikel (refereegranskat)abstract
- We prove the conjecture of A. Postnikov that (A) the number of regions in the inversion hyperplane arrangement associated with a permutation w is an element of (sic)(n). is at most the number of elements below w in the Bruhat order, and (B) that equality holds if and only if w avoids the patterns 4231, 35142, 42513 and 351624. Furthermore, assertion (A) is extended to all finite reflection groups. A byproduct of this result and its proof is a set of inequalities relating Betti numbers of complexified inversion arrangements to Betti numbers of closed Schubert cells. Another consequence is a simple combinatorial interpretation of the chromatic polynomial of the inversion graph of a permutation which avoids the above patterns.
|
|
| 40. |
- Håstad, Johan, et al.
(författare)
-
A smaller sleeping bag for a baby snake
- 2001
-
Ingår i: Discrete & Computational Geometry. - : Springer Science and Business Media LLC. - 0179-5376 .- 1432-0444. ; 26:1, s. 173-181
-
Tidskriftsartikel (refereegranskat)abstract
- By a sleeping bag for a baby snake in d dimensions we mean a subset of Rd which can cover, by rotation and translation, every curve of unit length. We construct sleeping bags which are smaller than any previously known in dimensions 3 and higher. In particular, we construct a three-dimensional sleeping bag of volume approximately 0.075803. For large d we construct d-dimensional sleeping bags with volume less than (cvlog d)d/d3d/2 for some constant c. To obtain the last result, we show that every curve of unit length in Rd lies between two parallel hyperplanes at distance at most C1d-3/2vlog d, for some constant c1.
|
|
