Wastlund's half-\bound conjecture for sorting permutations by block transpositions
Let an -permutation be a permutation of the entries , 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 .
Wastlund's conjecture. If and , then every -permutation can be sorted by at most
block transpositions.
The conjecture proposes a sharp upper bound matching the known lower bound for the decreasing permutation . 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
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.