Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The more trickier questions, found in exams from previous years, that seems to be using Ramsey Theorem.

  1. Prove that for every $ k \in \mathbb{N}$ exist $n=n(k)$ so that in every sequence of n different numbers, there exist either an ascending or descending subsequence of length $k$.

  2. Prove that for every $ k \in \mathbb{N}$ and every $ M \in \mathbb{R}$, there is $n$, so that for every family $F$ of $n$ unity circles in the plane, contains $k$ circles which have a common point, or $k$ circles so that the distance between any two of them is at least $M$.

In both of the questions I'm having a problem constructing an appropriate graph. Obviously, the vertices should represent the sequence in (1) and circles in (2), but I seem to get nowhere in the edges conditions (or coloring of $K_n$).

Thanks in advance for any help.

share|improve this question
1  
To learn a lot more about Ramsey Theory look at: Graham, R.; Rothschild, B.; Spencer, J. H. (1990), Ramsey Theory, New York: John Wiley and Sons Its an excellent book. –  Joseph Malkevitch Feb 5 '12 at 18:55
    
Thanks for the recommendation. For now it's only a small topic in a vast number of topics, that I need to know for the graph theory test. It's indeed one of the fascinating ones, and I will surely check this book in the near future. –  Pavel Feb 5 '12 at 19:21

2 Answers 2

up vote 3 down vote accepted

In general, you want to use Ramsey's theorem when you want to construct a large/infinite set of objects such that any $n$-sized group of them has a certain property. With that in mind, here's an example of how you can use Ramsey's Theorem on your two problems:

For (1), draw a blue edge between two elements of the sequence if they are ascending (i.e. the one that comes later in the sequence is the larger of the two) and draw a red edge if they are descending. By Ramsey's Theorem, we are done.

(2) is harder. The first obstacle is that there's no obvious disjunction: there are pairs of circles which do not touch yet are closer than $M$ apart, which really throws a wrench into the "obvious" Ramsey approach. However, we can try naively coloring any such pair of circles a third color and working with the 3-color version of Ramsey.

There's another obstacle, though. If we somehow get a set of $k$ circles such that each pair has a common point, there's still no guarantee that all of the circles have a common point. We can fix this too: instead of just saying that pairs of circles should have a common point, say that their centers should be less than 1/1000 units apart. If in a set of $k$ circles, any pair satisfies this, then all $k$ circles definitely have a point in common.

With this in mind, color a pair of circles red if their centers are less than 1/1000 units apart, blue if they're more than $M$ units apart, and orange if neither. Now, note that there's a limit on the number of circles we can have in an all-orange subgraph. In particular, any all-orange subgraph must fit inside a huge circle of radius $M$ - otherwise, some pairs will be blue. Also, each circle in an all-orange subgraph must have a small circle of radius 1/1000 to itself - otherwise, some pairs wil be red.

Therefore, by Pigeonhole, there's some number $B$ such that no all-orange subgraph has size $B$ or greater. Now we can finish it off: by Ramsey's Theorem, there's a number of circles so large that there's either a $B$-sized all-orange subgraph, a $k$-sized all-red subgraph, or a $k$-sized all-blue subgraph. The $B$-sized all-orange subgraph is impossible, so it must be one of the other two possibilities, and we are done.

Note that (2) might also be solved just using the Pigeonhole Principle. Ramsey's Theorem is almost never your only recourse, although it's really helpful to know!

share|improve this answer
    
Thanks! Very interesting technique in (2). It's funny, though, that I can't reason to myself the solution of (1). I thought of similar solution as well, but I just can't make a connection between a clique to ascending/descending subsequence (it seems that there can't be cycles, by the condition on edges). –  Pavel Feb 5 '12 at 19:05

I'll try to show 1. without using Ramsey's theorem.

Proof is by induction. It is clear that $n(2) = 2$. Assume $n(k) \le k!$. Now if we have a sequence of length $n(k) \cdot (k+1)$ then it can be grouped into $k+1$ contiguous subsequences of length $n(k)$ each of which by assumption includes either an ascending or a descending subsequence of length $k$. If at least one ascending group and at least one descending group are present, we can combine them to find an ascending or descending subsequence with length $k+1$. Without loss of generality, suppose all groups are ascending. If the maxima of each group are not descending, then we can form an ascending subsequence of length $k+1$ by adding a maximum which breaks the descent to the length $k$ ascending subsequence of the previous group. If the maxima are all descending, then again we have a length $k+1$ subsequence formed by the maxima themselves because there are $k+1$ groups. So $n(k+1) \le n(k) \cdot (k+1) \le (k+1)!$, and with the base case $n(2) \le 2!$, we have that $n(k) \le k!$ for all $k$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.