<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume11 Issue1" %>
A Non-Messing-Up Phenomenon for Posets
Bridget Eileen Tenner
Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139, USA
Annals of Combinatorics 11 (1) p.101-114 March, 2007
AMS Subject Classification: 06A07, 05A05, 05C30
We classify finite posets with a particular sorting property, generalizing a result for rectangular arrays. Each poset is covered by 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. We also characterize posets with more restrictive sorting properties.
Keywords: non-messing-up, partially ordered set, sorting, linear extension


1. H. Boerner, Darstellungen von Gruppen, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1955.

2. R.W. Cottle, J.L. Pietenpol, J. Luh, Row ordered and column ordered matrices, Amer. Math. Monthly 70 (1963) 212-213.

3. D. Gale and R.M. Karp, The non-messing-up theorem, preprint.

4. D. Gale and R.M. Karp, A phenomenon in the theory of sorting, J. Comput. System Sci. 6 (1972) 103-115.

5. D.E. Knuth, Private communication, May 2004.

6. D.E. Knuth, Sorting and Searching, The Art of Computer Programming, Vol. 3, Addison- Wesley, Reading, MA, 1973.

7. A. Postnikov, Affine approach to quantum Schubert calculus, Duke Math. J. 128 (3) (2005) 473-509.

8. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997.