MIT Combinatorics Seminar

A non-messing-up phenomenon for posets

Bridget Eileen Tenner  (MIT)

Friday, September 17, 2004    4:15 pm    Room 2-338


The Non-Messing-Up Theorem is a well known sorting result for rectangular arrays of real numbers. The result states that after first sorting the elements within each row of an array and then sorting within each column of the array, the rows remain sorted.

In this talk, we generalize this results to posets, completely defining the set of posets for which there exist two sets of disjoint saturated chains such that for any original labeling, after sorting the labels along both sets of chains, the labels of the chains in the first set remain sorted. This characterization relies on determining certain necessary conditions for posets to have the non-messing-up property, and in each case we exhibit the chain sets for which the property holds.

Finally we discuss non-messing-up posets with reduced redundancy for two notions of redundancy, and the distribution of linear extensions of non-messing-up posets obtained by sorting along the chain sets.