Monotonic subsequences in dimensions
higher than one
A.M.Odlyzko
AT&T Labs-Research
Murray Hill,NJ07974
email:amo@research.att
J.B.Shearer
IBM T.J.Watson Research Center
P.O.Box218
Yorktown Heights,NY10598
email:jbs@watson.ibm
R.Siders
AT&T Labs-Research
Murray Hill,NJ07974
email:siders@math.umn.edu
Dedicated to Herb Wilf on the occasion of his65-th birthday
Submitted:August31,1996;Accepted:November10,1996
Abstract
The1935result of Erd˝o s and Szekeres that any sequence of≥n2+1real numbers contains a monotonic subsequence of≥n+1terms 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 for2-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 rand
om from reasonable distributions,the average length of the longest monotonic subsequence is shown to be∼2n1/2as n→∞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,NJ07974
email:amo@research.att
J.B.Shearer
IBM T.J.Watson Research Center
Yorktown Heights,NY10598
email:jbs@watson.ibm
R.Siders
AT&T Labs-Research
Murray Hill,NJ07974
email:siders@math.umn.edu
Dedicated to Herb Wilf on the occasion of his65-th birthday
1.Introduction
A sequence y1,...,y k of real numbers is said to be monotonic if either y1≤y2≤···≤y k or y1≥y2≥···≥y k.A classic theorem of Erd˝o s and Szekeres[4]states that every sequence of m2+1real numbers has a monotonic subsequence of m+1 terms.Moreover,there do exist sequences of m2real numbers with no monotonic subsequences of length greater than m.This extremal result has led to research on a range of related problems in both extremal and average behavior.For references,see the survey of Mike Steele[13],and[11].
The result of Erd˝o s and Szekeres stimulated the question of what happens when in a sequence x1,...,x n,the real numbers x j are replaced by vectors x j from d-dimensional Euclidean space.Thefirst problem is to define what is meant by mono-tonicity for a subsequence in dimension d≥2.One way to do this is to say that a
subsequence x i
1,...,x i
k
,1≤i1<···<i k≤n,is monotonic if it is monotonic in
each coordinate(when the x j are presented in somefixed coordinate system).N.G. de Bruijn showed(see[8])that for this definition,a complete answer can be obtained from the Erd˝o s-Szekeres result.From a sequence of m2d+1vectors in d,a monotonic subsequence of m+1terms can be chosen,and this is best possible.
steele
A different generalization to higher dimensions,this time to relation spaces,was considered by J.B.Kruskal[8].In this case he was also able to obtain a complete answer using the Erd˝o s-Szekeres
result.
In this note we consider yet another generalization of monotonicity to vectors in
d that was proposed by Kruskal in[8].It is mor
e natural geometrically than the one considered by de Bruijn in that it is independent o
f the choice of the coordinate
system.There are several definitions(all shown to be equivalent to each other in
[8]).The one we will work with says that a sequence y1,...,y k,with y j∈ d for each j,is monotonic if there exists some nonzero w∈ d such that the sequence of
inner products(y1,w),...,(y k,w)is a monotonic sequence of real numbers.With this definition of monotonicity,any sequence of d+1points is monotonic.Also, since any nonzero w can be chosen,it is immediate by the Erd˝o s-Szekeres result[4] that a monotonic subsequence of≥ n1/2 points can be chosen from any sequence of n points.Kruskal conjectured that to guarantee the existence of a monotonic subsequence of length k≥d+1,it is necessary and sufficient that the total number of points
n satisfy n≥k2−kd−k+d+1.If Kruskal’s conjecture is true,then for every d,there will be sequences of points in d with longest monotonic subsequences of length(1+o(1))n1/2as n→∞.
As an aside,suppose we take y1,...,y n to be any of the sequences that are ex-
tremal for the Erd˝o s-Szekeres result,so that the y j are real numbers,and the longest
monotonic subsequence among them has length n1/2 .Let us now construct a se-quence in d by placing the y j on a line,say x j=(y j,0,...,0)for1≤j≤n.Then for any w∈ d with nonzerofirst coordinate,the longest monotonic subsequence of (x1,w),...,(x n,w)will have length n1/2 .However,for w=(0,1,0,...,0),we will have(x j,w)=0for all j,so for this w we will obtain a monotonic subsequence of length n.This shows that if we required strict monotonicity for the subsequences of the(x j,w),the problem would have a trivial solution.
We will show in Section2that if d isfixed and z1,...,z n are any n points in  d that are in general position,then as n→∞,almost all permutations x1,...,x n of z1,...,z n will have their longest monotonic subsequence of length(2+o(1))n1/2 as n→∞.In particular,if the z j are chosen independently at random from some continuous distribution on d(say uniform on the unit cube),and are permuted at random,then we will get maximal monotonic subsequences of length(2+o(1))n1/2 as n→∞with high p
robability.
Since most random choices give longest monotonic subsequences not much longer
than2n1/2for any d≥2,we get(asymptotically for n→∞)within a factor of2of what Kruskal’s conjecture predicts.However,that is the most that this method can do for us.On the other hand,in Section3we present an explicit construction of a sequence in d=2for which the longest monotonic subsequence has length≤n1/2+3. This shows that for d=2Kruskal’s conjecture is asymptotically tight.We expect that similar although more complicated constructions exist for all d≥3,and therefore that the asymptotic form of Kruskal’s conjecture is true for all dimensions.We do not know whether the exact form of Kruskal’s conjecture is correct.For d=2,we can improve our bound to≤n1/2+2,but we do not know whether our construction can be modified to give the full conjecture.
2.Average behavior
Ulam [15]was apparently the first one to ask about the distribution of L n ,the length of the longest increasing subsequence in a permutation of n distinct real num-bers.After initial work of Baer and Brock [1]and Hammersley [6],Logan and Shepp
[9]and Vershik and Kerov [16]proved the conjecture that L n tends to 2n 1/2in prob-ability as n →∞.Later it was shown by Frieze [5]that the distribution of L n is concentrated near its mean.Frieze’s result was subsequently sharpened by Bol-lob´a s and Brightwell [2]and Talagrand [14].Some of the fine structure details of the distribution of L n are still unknown.For full references,numerical evidence,and conjectures about the distribution of L n ,see [10]and [11].
In this paper we will use only two results.One follows from the lower bound of Logan and Shepp and of Vershik and Kerov:
Proposition 2.1For every  >0,
Prob(L n >(2− )n 1/2)→1as n →∞.(2.1)
The other result is a weak form of the upper bound that follows from the work of Frieze,of Bollob´a s and Brightwell,and of Talagrand.The result we will actually use follows also from the one-sided concentration result of J.-H.Kim [7],which is simpler to prove,but yields surprisingly strong bounds.(We will use only a weak version of Kim’s result.)
Proposition 2.2For all α, >0,there is a constant C =C (α, )such that
Prob(L n >(2+ )n 1/2)≤Cn −α.(2.2)
Let us now consider points z 1,...,z n ∈ d that are in general position (no 3on a line,no 4in a plane,etc.).For any nonzero w ∈ d ,permuting the z j induces a permutation of the inner products (z j ,w ).Hence Proposition 2.1shows immediately that if we permute the z j ,the resulting sequences x 1,...,x n will almost always have monotonic subsequences of length ≥(2+o (1))n 1/2as n →∞.
Suppose again that z 1,...,z n ∈ d are in general position,and suppose that x 1,...,x n is a permutation of z 1,...,z n .In determining monotonicity of subsequences of x 1,...,x n ,we only need to consider directions w that satisfy d −1linearly inde-pendent constraints of the form (w,z i −z j )=0.(Suppose we move w continuously without hitting any additional conditions (w,z i )=(w,z j ),and without destroying any conditions of this type that held before.Then the relative positions of the (w,z i )do not change,and when we do add an additional relation (w,z i )=(w,z j ),longest monotone subsequences can only grow.)However,there are fewer than  n 2 d −1
such directions w .For each w ,a random permutation of z 1,...,z n gives a random per-mutation of the n −2(d −1)numbers (w,z j )for which (w,z j )is unique.We apply Proposition 2.2to those,and conclude that the probability of a monotone subse-quence of length ≥(2+ )n 1/2+2d is ≤n −10d for n s
ufficiently large.Hence the probability of a monotone subsequence of length ≥(2+ )n 1/2+2d for any of the ≤n 2d directions w that need to be considered is o (1)as n →∞.
Combining the results proved above,we obtain the following result.
Theorem2.1If z1,...,z n∈ d are in general position,and are permuted at ran-dom,then for any >0,the length M n of the longest monotonic subsequence in the permuted sequence satisfies
Prob((2− )n1/2≤M n≤(2+ )n1/2)→1as n→∞.(2.3) The restriction to general positions in Theorem2.1is important,since z1=z2=···=z n=0produces dramatically different behavior.
Theorem2.1determines the typical asymptotic behavior of the length of the longest monotonic subsequence in d.The same methods can also be used to study the expected lengths of unimodal and related subsequences,if those notions are extended to d in the same way.(For d=1,these questions were answered by Chung[3]and Steele[12].)
3.Extremal sequences
Section2showed that for any d≥2,there do exist sequences x1,...,x n∈ d with longest monotonic subsequences of length(2+o(1))n1/2as n→∞.That is within a factor of2of what Kruskal’s conjecture p
redicts.In this section we show that for d=2,we can construct sequences of points that gain that factor of2,and so come close to proving Kruskal’s conjecture.(Our construction yields sequences that in which the longest monotonic subsequences are longer by at most2than those predicted to exist by Kruskal’s conjecture.A careful examination of our proof shows that we can decrease our upper bound by1,and thus be at most1worse than Kruskal’s conjecture.)
Theorem3.1For any n∈ +,there exists a sequence of points x1,...,x n∈ 2 which has no monotonic subsequence of length> n1/2 +2.
Proof.Wefirst use induction to construct,for all k∈ +and0< <1/10,a sequence of points z1,...,z k∈ 2with the following properties:
(i)the angle between any two lines determined by pairs of the z j is< .
(ii)If the line through z1and z k is turned in a counterclockwise direction,the projections of the z j on that line appearfirst in the order
z1,z2,...,z k.
Then,as the line keeps turning,z1moves past z2,so the order becomes
z2,z1,z3,...,z k.
Then z1moves past z3,...,z k,in turn,while the order of those points remains unchanged,until the order becomes
z2,z3,...,z k,z1.
Next,as the line continues turning,z k moves past z k −1,then past z k −2,...,and finally z 2to create the order of projections
z k ,z 2,z 3,...,z k −1,z 1.
Next,z 2moves past z 3,then z 4,...,until the order is
z k ,z 3,z 4,...,z k −1,z 2,z 1,
and then z k −1starts moving past z k −2,....In the end,when the rotation reaches 180◦,we see the reversed order
z k ,z k −1,...,z 2,z 1.
(iii)If we look at the points z j in the order z 1,z k ,z 2,z k −1,z 3,z k −2,...,then any
point z j lies inside the triangle determined by the preceding three points in this ordering.
To start the induction,for k =1we choose z 1to be a point,for k =2let z 1and z 2be any two distinct points,and for k =3let z 1,z 2,and z 3be the three points in Fig.1that are labeled z 1,z 2,and z k ,respectively.Suppose that we can construct I (k −2,  )for any 0<  <1/10.We next proceed to construct I (k, )for any  with 0< <1/10as follows.Let z 1=(0,0),z k =(4,0),and scale and translate
I (k −2, /1000)so that if its points are z  1,...,z  k −2,then
z  1=(2,− /10),z  k −2=(3,−49 /1000).
(See Fig.1for this construction.)If we then let z j =z  j −1,2≤j ≤k −1,we easily
see that the sequence z 1,z 2,...,z k satisfies all the conditions for I (k, ).
z z k
2
z k-1z 1
Figure 1:Construction of points z 1,z 2,...,z k .
We now proceed to prove Theorem 3.1.It suffices to construct a sequence x 1,...,x n satisfying the conditions of this theorem for n =m 2.Let z 1,...,z n be the sequence of points I (n,1/100)constructed above.We now rearrange them into the sequence

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。