Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Monotonic subsequences in dimensions higher than one. | Monotonic subsequences in dimensions higher than one A. M. Odlyzko AT T Labs - Research Murray Hill NJ 07974 email amo@ J. B. Shearer IBM T. J. Watson Research Center . Box 218 Yorktown Heights NY 10598 email jbs@ R. Siders AT T Labs - Research Murray Hill NJ 07974 email siders@ Dedicated to Herb Wilf on the occasion of his 65-th birthday Submitted August 31 1996 Accepted November 10 1996 Abstract The 1935 result of Erdos and Szekeres that any sequence of n2 1 real numbers contains a monotonic subsequence of n 1 terms has stimulated extensive further research including a paper of J. B. Kruskal that defined an extension of monotonicity for higher dimensions. This paper provides a proof of a weakened form of Kruskal s conjecture for 2-dimensional Euclidean space by showing that there exist sequences of n points in the plane for which the longest monotonic subsequences have length n1 2 3. Weaker results are obtained for higher dimensions. When points are selected at random from reasonable distributions the average length of the longest monotonic subsequence is shown to be 2n1 2 as n 1 for each dimension. AMS-MOS Subject Classification Primary 05A05 Secondary 06A07 60C05. Monotonic subsequences in dimensions higher than one A. M. Odlyzko AT T Labs - Research Murray Hill NJ 07974 email amo@ J. B. Shearer IBM T. J. Watson Research Center Yorktown Heights NY 10598 email jbs@ R. Siders AT T Labs - Research Murray Hill NJ 07974 email siders@ Dedicated to Herb Wilf on the occasion of his 65-th birthday 1. Introduction A sequence y1 . yk of real numbers is said to be monotonic if either y1 y2 yk or y1 y2 yk. A classic theorem of Erdos and Szekeres 4 states that every sequence of nr 1 real numbers has a monotonic subsequence of m 1 terms. Moreover there do exist sequences of m2 real numbers with no monotonic subsequences of length greater than m. This extremal result has led to research on a
