This web page contains the abstract of my paper:
"Montonic subsequences in dimensions higher than one", with A. M. Odlyzko and R. Siders, The Electronic Journal of Combinatorics, 4(2)(1997), #R14.
Abstract: The 1935 result of Erdos and Szekeres that any sequence of at least n**2+1 real numbers contains a monotonic subsequence of at least 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 exists a sequence of n points in the plane for which the longest monotonic subsequences have length at most n**(1/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 about 2*n**(1/2) as n goes to infinity for each dimension.
IBM Research home page |
James B. Shearer's home page |
[ IBM home page | Order | Search | Contact IBM | Legal ]