Thread: Colour Number Graph

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

Let 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:

Wich suggests that the result can be proven by seeing the numbers as vertices in the graph . Why this helps...I don't quite see this, yet.

Any suggestions?

Originally Posted by Dinkydoe

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

Let 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:

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

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: and

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 equals (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 . Now apply a l-colouring on G.

Note that, by the pigeon-hole principle 1 colour is used at least k+1 times.
All that have this colour form a decreasing subsequence of at least k+1 terms.