At the conference Dress defined parity split maps by triple point distance and asked for a characterisation of such maps coming from binary phylogenetic X-trees. This article gives an answer to that question. The characterisation for X-trees can be easily described as follows: If all restrictions of a split map to sets of five or fewer elements is a parity split map for an X-tree, then so is the entire map. To ensure that the parity split map comes from an X-tree which is binary and phylogenetic, we add two more technical conditions also based on studying at most five points at a time.

A note on blockers in posets2004In: Annals of Combinatorics, ISSN 0218-0006, E-ISSN 0219-3094, Vol. 8, no 2, p. 123-131Article in journal (Refereed)

Abstract [en]

The blocker A* of an antichain A in a finite poset P is the set of elements minimal with the property of having with each member of A a common predecessor. The following is done: (1) The posets P for which A** = A for all antichains are characterized.(2) The blocker A* of a symmetric antichain in the partition lattice is characterized.(3) Connections with the question of finding minimal size blocking sets for certain set families are discussed.

Extending to r > 1 a formula of the authors, we compute the expected reflection distance of a product of t random reflections in the complex reflection group G (r, 1, n). The result relies on an explicit decomposition of the reflection distance function into irreducible G (r, 1, n) characters and on the eigenvalues of certain adjacency matrices.

We study the length L-k of the shortest permutation containing all patterns of length k. We establish the bounds e(-2)k(2) < L-k <= (2/3 + o(1))k(2). We also prove that as k there are permutations of length (1/4+o(1))k(2) containing almost all patterns of length k.

In this paper, we give an algorithm for computing the Kazhdan-Lusztig R-polynomials in the symmetric group. The algorithm is described in terms of permutation diagrams. In particular we focus on how the computation of the polynomial is affected by certain fixed points. As a consequence of our methods, we obtain explicit formulas for the R-polynomials associated with some general classes of intervals, generalizing results of Brenti and Pagliacci.

We generalize the definition of a pattern from permutations to alternating sign matrices. The number of alternating sign matrices avoiding 132 is proved to be counted by the large Schroder numbers, 1, 2, 6, 22, 90, 394,.... We give a bijection between 132-avoiding alternating sign matrices and Schroder paths, which gives a refined enumeration. We also show that the 132-, 123-avoiding alternating sign matrices are counted by every second Fibonacci number.

Let 1 (d) (M-m,M-n; Z) not equal 0. Second, for each k >= 0, we show that there is a polynomial f(k)(a, b) of degree 3k such that the dimension of (H) over tilde (k+a+2b-2) (M-k+a+3b-1,M- k+2a+3b-1; Z(3)), viewed as a vector space over Z(3), is at most f(k)(a, b) for all a >= 0 and b >= k+ 2. Third, we give a computer- free proof that (H) over tilde (2) (M-5,M-5; Z) congruent to Z(3). Several proofs are based on a new long exact sequence relating the homology of a certain subcomplex of M-m,M-n to the homology of M-m-2,M-n-1 and M-m-2,M-n-3.