A Lemma and a Conjecture on the Cost of Rearrangements

Abstract

Consider a stack of books, containing both white and black books. Suppose that we want to sort them out, putting the white books on the right, and the black books on the left (fig.~1). This will be done by a finite sequence of elementary transpositions. In other words, if we have a stack of all black books of length $a$ followed by a stack of all white books of length $b$, we are allowed to reverse their order at the cost of $a+b$. We are interested in a lower bound on the total cost of the rearrangement.

2 figures, 4 pages

Cited by in corpus (8)

• Mixing and Un-mixing by Incompressible Flows
• Anomalous Dissipation in Passive Scalar Transport
• Properties of Mixing BV vector fields
• Lagrangian flows for vector fields with anisotropic regularity
• On the energy-constrained optimal mixing problem for one-dimensional initial configurations
• Differential Equations with singular fields
• Numerical Evidence of Exponential Mixing by Alternating Shear Flows
• The Cost of Two-dimensional Rearrangement