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

About 18 years old · traced to

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 12⋯n12\cdots n.

Wastlund's conjecture. If n≠13n\neq 13 and n≠15n\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(n−1)⋯21n(n-1)\cdots 21. The supplied text gives no resolution status for the conjecture.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.