Partitioning permutations into monotone subsequences (Q820846)

Summary: A permutation is \(k\)-coverable if it can be partitioned into \(k\) monotone subsequences. Barber conjectured that, for any given permutation, if every subsequence of length \(\binom{k+2} {2}\) is \(k\)-coverable then the permutation itself is \(k\)-coverable. This conjecture, if true, would be best possible. Our aim in this paper is to disprove this conjecture for all \(k \geqslant 3\). In fact, we show that for any \(k\) there are permutations such that every subsequence of length at most \((k/6)^{2.46}\) is \(k\)-coverable while the permutation itself is not.