A lemma and a conjecture on the cost of rearrangements

By Alberto Bressan. 2003

88 citations recorded by the source corpus.

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 a1b. We are interested in a lower bound on the total cost of the rearrangement. Assume that initially the white and black books are highly mixed. By this we mean that inside every segment of length e one can find at least ke white books and at least ke black books, for a given k ]0 , 1[. We want to show that, as eK0, the cost of sorting the books grows like N log eN. We reformulate the problem in more precise terms. Consider the set F of all piecewise constant functions f : [0 , 1 ] O ]0, 1(. We think of B u ]x ; f (x)41( as the set of black books. We say that g is obtained from f by an elementary transposition if the following holds. For some y [0 , 1[ and a , bD0, one has

Subfields: Genetics

View Paper: https://www.semanticscholar.org/paper/9cc329520fc22d1f971b54e87f602245ef1ecb31

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Genetics

1. F. Bouchut
2. Luigi Ambrosio
3. Gianluca Crippa
4. Camillo De Lellis
5. C. Ketterer

Citations in the corpus

• Estimates and regularity results for the DiPerna-Lions flow (2008, background): “Then in [7] the following conjecture is proposed: Conjecture 6.”
• Lagrangian flows for vector fields with gradient given by a singular integral (2012, background): “A full extension of our proof to the case of a measure would imply a proof of Bressan’s compactness conjecture [11, 10], together with other deep consequences.”
• Exponential self-similar mixing and loss of regularity for continuity equations (2014, background): “The second notion (see [5]) is geometric and has been introduced for solutions with value ±1: Definition 2.”
• The Flow Associated to Weakly Differentiable Vector Fields: Recent Results and Open Problems (2011, background): “An application to a conjecture on mixing flows In [47] the author considers a problem on mixing vector fields on the two-dimensional torus K = R2/Z2.”
• Existence, Uniqueness, Stability and Differentiability Properties of the Flow Associated to Weakly Differentiable Vector Fields (2009, background): “An application to a conjecture on mixing flows In [47] the author considers a problem on mixing vector fields on the two-dimensional torus K = R2/Z2.”