Wastlund's half-\bound conjecture for sorting permutations by block transpositions
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.
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
Sign in to submit a solution.
No solutions have been posted yet.