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.

arXiv comment2 figures, 4 pages

Cited by in corpus (21)

• Lower bounds on the mix norm of passive scalars advected by incompressible enstrophy-constrained flows
• Maximal mixing by incompressible fluid flows
• Lagrangian flows for vector fields with gradient given by a singular integral
• Sharp regularity estimates for solutions of the continuity equation drifted by Sobolev vector fields
• An algebraic reduction of the `scaling gap' in the Navier-Stokes regularity problem
• On geometric and analytic mixing scales: comparability and convergence rates for transport problems
• Mixing and Un-mixing by Incompressible Flows
• Regularity estimates for the flow of BV autonomous divergence free vector fields in ${\mathbb{R}}^2$
• Mixing and diffusion for rough shear flows
• Anomalous Dissipation in Passive Scalar Transport
• Properties of Mixing BV vector fields
• The Batchelor spectrum of passive scalar turbulence in stochastic fluid mechanics at fixed Reynolds number
• The space $B_{\infty ,\infty }^{-1}$, volumetric sparseness, and 3D NSE
• On the energy-constrained optimal mixing problem for one-dimensional initial configurations
• Stable mixing estimates in the infinite Péclet number limit
• Lagrangian flows for vector fields with anisotropic regularity
• Singular integrals and a problem on mixing flows
• An Overview on Some Results Concerning the Transport Equation and its Applications to Conservation Laws
• Differential Equations with singular fields
• Numerical Evidence of Exponential Mixing by Alternating Shear Flows
• The Cost of Two-dimensional Rearrangement