The Non-Messing-Up Theorem,

Abstract

The paper is concerned with the ordering of certain sets in different ways. A typical example is a rectangular array of playing cards which can be ordered so that either (a) the rows are in increasing order left to right or (b) the columns are in increasing order top to bottom. It turns out that if the rows are initially ordered then they remain so even after one has ordered the columns. The paper proves this as a special case of a considerably more general non-messing-up phenomenon. (Author)

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1971
Accession Number
AD0721356

Entities

People

  • David Gale
  • Richard M. Karp

Organizations

  • University of California, Berkeley

Tags

Fields of Study

  • Mathematics

Readers

  • Combustion Dynamics and Shock Wave Physics.
  • Graph Algorithms and Convex Optimization.
  • Strategic Security Studies