Geodesic
Monotonic subsequences in dimensions higher than one
The electronic journal of combinatorics, The Wilf Festschrift volume, Tome 4 (1997) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 furher 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 $n^{2}+2$ or less.. Weaker results are also obtained for higher dimensions. The average length of the longest increasing monotonic subsequence is shown to be $\sim 2n^{1/2}$ as $n\rightarrow\infty$ for each dimension.
DOI : 10.37236/1329
Classification : 05A05, 06A07, 60C05
Mots-clés : monotonic subsequence, Kruskal's conjecture 
@article{10_37236_1329,
     author = {A. Odlyzko and J. B. Shearer and R. Siders},
     title = {Monotonic subsequences in dimensions higher than one},
     journal = {The electronic journal of combinatorics},
     year = {1997},
     volume = {4},
     number = {2},
     doi = {10.37236/1329},
     zbl = {0884.05001},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1329/}
}
TY  - JOUR
AU  - A. Odlyzko
AU  - J. B. Shearer
AU  - R. Siders
TI  - Monotonic subsequences in dimensions higher than one
JO  - The electronic journal of combinatorics
PY  - 1997
VL  - 4
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1329/
DO  - 10.37236/1329
ID  - 10_37236_1329
ER  - 
%0 Journal Article
%A A. Odlyzko
%A J. B. Shearer
%A R. Siders
%T Monotonic subsequences in dimensions higher than one
%J The electronic journal of combinatorics
%D 1997
%V 4
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/1329/
%R 10.37236/1329
%F 10_37236_1329
A. Odlyzko; J. B. Shearer; R. Siders. Monotonic subsequences in dimensions higher than one. The electronic journal of combinatorics, The Wilf Festschrift volume, Tome 4 (1997) no. 2. doi: 10.37236/1329

Cité par Sources :