Results 1 to 3 of 3

Thread: Colour Number Graph

  1. #1
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411

    Colour Number Graph

    Hey, I'm a little stuck on the following problem:

    Let $\displaystyle x_1,\cdots x_{kl+1}$ be n different real numbers. Show there exists a decreasing subsequence with at least k+1 terms, or a increasing sequence of at least l+1 terms. With as hint: $\displaystyle \chi(K_{lk+1})>lk$

    Wich suggests that the result can be proven by seeing the numbers $\displaystyle x_i$ as vertices in the graph $\displaystyle K_{lk+1}$. Why this helps...I don't quite see this, yet.

    Any suggestions?
    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
    Quote Originally Posted by Dinkydoe View Post
    Hey, I'm a little stuck on the following problem:

    Let $\displaystyle x_1,\cdots x_{kl+1}$ be n different real numbers. Show there exists a decreasing subsequence with at least k+1 terms, or a increasing sequence of at least l+1 terms. With as hint: $\displaystyle \chi(K_{lk+1})>lk$

    Wich suggests that the result can be proven by seeing the numbers $\displaystyle x_i$ as vertices in the graph $\displaystyle K_{lk+1}$. Why this helps...I don't quite see this, yet.

    Any suggestions?

    It's well known theorem. Erdos-Szekeres Theorem.

    You can find many proofs on the net.

    Here some nice(and very difficult) article about this theorem...
    http://www-stat.wharton.upenn.edu/~s...VOTMSTOEAS.pdf
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411

    Re: Colour Number Graph

    Thanks, it's a nice article.

    I did prove it differently though, ...but it's depending on (again) difficult graph-theory.

    We can construct a graph: $\displaystyle (x_i,x_j) \in G \Leftrightarrow j>i$ and $\displaystyle x_j>x_i$

    The increasing subsequences form a clique in G. Furthermore, G is a comparability graph...and by some theorems, G must be a perfect graph.

    A perfect graph has the property that the colour number $\displaystyle \chi(G)$ equals $\displaystyle \alpha(G)$ (wich is the clique-number,i.e., largest clique in G).

    Suppose there's no increasing subsequence of at least l+1 terms. Then we have $\displaystyle \alpha(G)=\chi(G)\leq l$. Now apply a l-colouring on G.

    Note that, by the pigeon-hole principle 1 colour is used at least k+1 times.
    All $\displaystyle x_i$ that have this colour form a decreasing subsequence of at least k+1 terms.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 15th 2011, 09:59 AM
  2. Replies: 2
    Last Post: Feb 10th 2011, 11:09 PM
  3. possible colour choices
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Aug 2nd 2010, 11:16 PM
  4. All horses are the same colour?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 24th 2008, 04:57 PM
  5. Five Colour Map
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: May 30th 2005, 01:47 PM

Search Tags


/mathhelpforum @mathhelpforum