Results 1 to 2 of 2

Math Help - Dilworth’s theorem

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    8

    Dilworth’s theorem

    Hi Guys I really in trouble with a problem about dilwor theorem

    The problem states:

    Let a_1 , a_2 , . . . , a_{ <br />
n^2 +1} be a permutation of the integers
    1, 2, . . . , n^2 + 1 . Show that Dilworth’s theorem implies that the
    sequence has a subsequence of length n + 1 that is monotone.

    Thanks a lot to all of you

    All the best

    joksy
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by joksy View Post
    Hi Guys I really in trouble with a problem about dilwor theorem

    The problem states:

    Let a_1 , a_2 , . . . , a_{ <br />
n^2 +1} be a permutation of the integers
    1, 2, . . . , n^2 + 1 . Show that Dilworth’s theorem implies that the
    sequence has a subsequence of length n + 1 that is monotone.

    Thanks a lot to all of you

    All the best

    joksy
    Hi joksy,

    Here's a hint.

    I think the trick is to define a partial order on {1, 2, \dots , n^2+1} as follows:

    Define i \leq j if
    i \leq j \text{ and } a_i \leq a_j (in the usual ordering of the integers).

    Think about what constitutes a chain and an antichain in this ordering (in relation to ascending or descending subsequences), then apply Dilworth's theorem, and I think you will get it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  2. Replies: 3
    Last Post: May 14th 2010, 10:04 PM
  3. Prove Wilson's theorem by Lagrange's theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 10th 2010, 01:07 PM
  4. Replies: 2
    Last Post: April 3rd 2010, 04:41 PM
  5. Replies: 0
    Last Post: November 13th 2009, 05:41 AM

Search Tags


/mathhelpforum @mathhelpforum