Wastlund's half-\bound conjecture for sorting permutations by block transpositions

From papers

Let an nn-permutation be a permutation of the entries 1,2,,n1,2,\ldots,n, and let a block transposition interchange two adjacent blocks of entries. A series of such operations sorts a permutation if it transforms it into the increasing permutation 12n12\cdots n.

Wastlund's conjecture. If n13n\neq 13 and n15n\neq 15, then every nn-permutation can be sorted by at most

(n+1)/2\lceil (n+1)/2 \rceil

block transpositions.

The conjecture proposes a sharp upper bound matching the known lower bound for the decreasing permutation n(n1)21n(n-1)\cdots 21. The supplied text gives no resolution status for the conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Miklos Bona and Ryan Flynn, “Sorting a Permutation by block moves”, arXiv:0806.2787 (2008).

Solutions 0

No solutions have been posted yet.