Name
Abstract | ||
|---|---|---|
The 1935 result of Erd} os 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 deflned 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!1for each dimension. |
Year | Venue | Keywords |
|---|---|---|
1997 | Electr. J. Comb. | euclidean space,2 dimensional |
DocType | Volume | Issue |
Journal | 4 | 2 |
Citations | PageRank | References |
1 | 1.22 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew M. Odlyzko | 1 | 1286 | 413.71 |
| James B. Shearer | 2 | 277 | 79.48 |
| Ryan C. Siders | 3 | 30 | 10.04 |