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.