Hi bobby,

what do you mean by "contiguous" here?

Ah! Yes, we skip!

Sure. In the lecture we had the following version of Erdos/Szerkeres which applies to continuous data as well:

Let

Hi

I cross-checked the paper and this is clearly way to complicated as we usually solve those exercises with one page maximum. One can attend this lecture from the third year or higher.

Unfortunately not. But I could scan you the respective page from the notes. Is there a possibility to upload it here?

Mmh, I am really a newbie

1. Post a reply - ok
2. upload - how/where? I see no button and cannot use "[img][/img]"

Logging in is sometimes helpful ...

Uploaded Images

Cool. Thanks in advance for your help!

Hi bobbym!

I solved the problem. Please find my tex code below (compile yourself for better reading, sry!)

Cheers
Michael

We want to determine a strategy to select an increasing subsequence of $x_1,...,x_n$. Let $Y$ be the length of our increasing subsequence. As $X$ is defined as the longest increasing subsequence we surely have $E[X] \ge E[Y]$. Depending on how good our strategy is we hope to get $E[Y] \ge (1-o(1))(1-\frac{1}{e})\sqrt{n}$ which would complete the proof.

Let us assume that $m:= \sqrt{n}$ is an integer and partition our random sequence in blocks $L_j=(x_{(j-1)m+1},...,x_{jm} )$ for $j=1,...,m$ (we can assume this as we look at asymptotics in $n$ in the end).

The strategy picks the first number $y_1$ out of $x_1,...,x_n$ that is $\le \frac{1}{m}$ and skips to the next block. It then continuous to pick a number $y_i$ in each of the remaining blocks if $y_{i-1} \le y_i \le y_{i-1} + \frac{1}{m}$ and skips this block otherwise. At the end we receive an increasing subsequence $y_1,...,y_Y$ of length $Y$.

input: sequence x(1),...x(n)
output: length Y of an increasing subsequence y(1)<=...<=y(Y)

Y = 0         \\ counting the length of the subsequence
s = zero array     \\ storing the subsequence here

\\ go through intervals elements of L_j
for j = 1 to m   
{
   \\ boolean helper to implement stopping time, i.e. breaking condition for the loop
   success == 0
   while (success == 0) do
   {
      \\ go through elements of L_j
      for k = (j-1)*m+1 to j*m 
      {
         \\ find a larger element which is still small enough
         if (s(Y) <= x_k <= s(Y)+1/m)     
         {
            Y = Y+1       \\ length of subsequence ++
            s(Y) = x_k      \\ store element
            success == 1   \\ stop searching in L_j 
                     \\ and go to next interval
         }
      }
   }
}

return(Y)

Now let us estimate the expectation of $Y$,

\begin{alignat*}{1}
E[Y] &= E[\sum_{j=1}^{m} \mathds{1}_{\{ \text{ "found suitable number in }L_j\text{ " }\}}]\\
&= \sum_{j=1}^{m}E[ \mathds{1}_{\{ \text{ "found suitable number in }L_j\text{ " }\}}]
\end{alignat*}

As our "tolerance of increase" $\frac{1}{m}$ stays the same for all numbers we search for, all $x_i$ are independently and uniformly distributed and all parts of the sequence $L_j$ contain the same amount of numbers $m$ we get that

\begin{alignat*}{1}
E[Y] &= m P[ \text{ "found suitable number in }L_1 \text{ " }]\\
&= m (1- P[\forall i=1,...,m : x_i > \frac{1}{m}]) \\
&= m (1- (P[x_1 > \frac{1}{m}])^m) \\
&= m (1- (1- \frac{1}{m})^m) \\
&= \sqrt{n} (1- (1- \frac{1}{\sqrt{n}})^{\sqrt{n}}) \\
&= (1-o(1))(1-\frac{1}{e})\sqrt{n}.
\end{alignat*}

So our strategy gives the lower bound $E[X] \ge E[Y]$.

Hi naumberg

You can use the math tag {math}{/math} except that the brackets are square and not curly...