Partitioning permutations into monotone subsequences

DOI10.37236/10267MaRDI QIDQ820846zbMATH OpenOpenAlexFDO

Authors David Wärn

Publication date 28 September 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2102.10328

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal set theory (05D05)

Abstract: 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 $k+2choose2$ 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 $kge3$. 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.

Review text

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.

Recommendations

• The minimum number of monotone subsequences
• Monotone subsequences in high-dimensional permutations
• scientific article; zbMATH DE number 3880704
• scientific article; zbMATH DE number 3997796
• Covering \(n\)-permutations with \((n+1)\)-permutations

Cites work

• Critical 3-cochromatic graphs
• Generalized split graphs and Ramsey numbers
• scientific article; zbMATH DE number 3903967 (Why is no real title available?)
• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 3611388 (Why is no real title available?)
• Improved bounds for the sunflower lemma
• Matrix partitions of perfect graphs
• Partitioning permutations into increasing and decreasing subsequences

Cited in

(3)

• Permutations with exactly one copy of a monotone pattern of length \(k\), and a generalization
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• Forbidden patterns in mixed linear layouts

This page was built for publication: Partitioning permutations into monotone subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820846)