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.
Originally Posted by Dinkydoe
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...
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: 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.