tailieunhanh - Báo cáo toán học: "The minimum number of monotone subsequences"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: The minimum number of monotone subsequences | The minimum number of monotone subsequences Joseph Samuel Myers Department of Pure Mathematics and Mathematical Statistics Centre for Mathematical Sciences Wilberforce Road Cambridge CB3 0WB United Kingdom Submitted Jul 4 2002 Accepted Nov 25 2002 Published Dec 13 2002 MR Subject Classifications 05A05 05C35 05D10 Abstract Erdos and Szekeres showed that any permutation of length n k2 1 contains a monotone subsequence of length k 1. A simple example shows that there need bp no morp than tn mod ĩUếd Ạh fc tn mod ZjlltOAJ snob siilisooiipiii Ps WP ưe no moi e L nan n m u rv J y k 1 y n m u rv J J y k 1 y suưseq uences w e conjecture that this is the minimum number of such subsequences. We prove this for k 2 with a complete characterisation of the extremal permutations. For k 2 and n k 2k 1 we characterise the permutations containing the minimum number of monotone subsequences of length k 1 subject to the additional constraint that all such subsequences go in the same direction all ascending or all descending we show that there are 2 nm i k C 22k 2 such extremal permutations where Ck k i 2kk is the kth Catalan number. We conjecture with some supporting computational evidence that permutations with a minimum number of monotone k 1 -subsequences must have all such subsequences in the same direction if n k 2k 1 except for the case of k 3 and n 16. 1 Introduction A well-known result of Erdos and Szekeres 2 may be expressed as follows Theorem 1 Erdos and Szekeres 2 Let n and k be positive integers. If n k2 1 then in any permutation of the integers 0 1 . n 1 there is a monotone subsequence of length k 1. Research supported by EPSRC studentship 99801140. THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2 2002 R4 1 This problem leads to many variations a survey of which has been made by Steele 5 . Here we consider an extremal problem that arises as a variation this problem was posed by Mike Atkinson Michael Albert and Derek Holton. If n k2 1 then we .