Wastlund's half-\bound conjecture for sorting permutations by block transpositions
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.