# Colour Number Graph

• Jun 1st 2011, 05:19 AM
Dinkydoe
Colour Number Graph
Hey, I'm a little stuck on the following problem:

Let $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: $\chi(K_{lk+1})>lk$

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

Any suggestions?
• Jun 10th 2011, 10:37 AM
Also sprach Zarathustra
Quote:

Originally Posted by Dinkydoe
Hey, I'm a little stuck on the following problem:

Let $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: $\chi(K_{lk+1})>lk$

Wich suggests that the result can be proven by seeing the numbers $x_i$ as vertices in the graph $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.

http://www-stat.wharton.upenn.edu/~s...VOTMSTOEAS.pdf
• Jun 17th 2011, 05:26 AM
Dinkydoe
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: $(x_i,x_j) \in G \Leftrightarrow j>i$ and $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 $\chi(G)$ equals $\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 $\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 $x_i$ that have this colour form a decreasing subsequence of at least k+1 terms.