Results 1 to 2 of 2

Math Help - Erdos-Szekeres theorem

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Erdos-Szekeres theorem

    This concerns a more general version of the Erdos-Szekeres theorem.

    a) Prove: For m,n \geq1, if S is a sequence of mn + 1 distinct real numbers, then S contains either an increasing subsequence of length m + 1 or a decreasing subsequence of length n + 1.

    Given a sequence S of mn + 1 distinct real numbers x_{1},x_{2},\ldots,x_{mn+1}, place these elements into a set of ordered columns as follows:

    Place x_{1} at the top of the first column. For each subsequent x_{i}, if x_{i} is greater than the value that is on top of a column, put that  x_{i} on top of the first such column, otherwise start a new column with that x_{i}.

    The elements of any column correspond to an increasing subsequence. Also note that we only shift to a later column when the  x_{i} was smaller than all the top numbers of the previous columns. The top numbers of the columns form a decreasing subsequence. By the pigeon hole principle, if we have n or fewer columns then at least one of the columns must contain greater than m members since we started with mn+1 elements. Similarly, if every column contains m or fewer members we must have greater than n columns. QED

    b) Prove that this result is best possible by showing that the result doesn't necessarily hold when mn + 1 is replaced by mn.

    Using the same argument as above we could have n columns but only m members in each column. Therefore we could only guarantee subsequences of m increasing and n decreasing members. QED

    Is the reasoning for a and b correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    My way to...

    b.

    Obtain on following sequence: (there is no increasing sequence of length n+1

    We start with:

    (m-1)n+1,(m-1)n+2,...,(m-1)n+n=mn

    then,

    (m-2)n+1,(m-2)n+2,...,(m-2)n+n=(m-1)n

    and so on to:

    1,2,...,n


    Obtain on following sequence: (there is no decreasing sequence of length m+1


    We start with:

    m,2m,...,nm

    proceed with:

    m-1,2m-1,...,nm-1
    and so on to:

    1,m+1,(n-1)m+1


    Actually we proved that theorem is "Tightly bound"


    Good-Luck!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Erdos-Ginzburg-Ziv Theorem...
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: January 3rd 2011, 11:03 AM
  2. Erdos-Szekeres Theorem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 6th 2010, 02:18 PM
  3. Erdos Ginzburg Ziv Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 7th 2010, 09:09 PM
  4. Erdos-Szekeres generalization
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 18th 2009, 02:35 AM
  5. Erdos-Szekeres variation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 17th 2009, 02:22 PM

Search Tags


/mathhelpforum @mathhelpforum