which tells us that glorified Ramsey’s theorem is undecidable in P, requires a deeper analysis of nonstandard models than that undertaken in the preceding chapter, and is beyond the scope of a book such as this one.

Problems

26.1Show that at a party attended by at least nine persons, any two of whom either like each other or dislike each other, either there are four, any two of whom like each other, or there are three, any two of whom dislike each other.

26.2Show that at a party attended by at least eighteen persons, any two of whom either like each other or dislike each other, either there are four, any two of whom like each other, or there are four, any two of whom dislike each other.

26.3A finite set of points in the plane, none lying on the line between any other two, is said to be convex if no point lies in the interior of the triangle formed by any three other points, as on the left in Figure 26-3. It is not hard to show that given

Figure 26-3. Convex and concave sets of points.

any set of five points in the plane, none lying on the line between any other two, there is a convex subset of four points. The Erdos¨–Szekeres theorem states that, more generally, for any number n > 4 there exists a number m such that given a set of (at least) m points in the plane, none lying on the line between any other two, there is a convex subset of (at least) n points. Show how this theorem follows from Ramsey’s theorem.

26.4Show that the general case of Ramsey’s theorem follows from the special case with s = 2, by induction on s.

26.5For r = s = 2 and n = 3, each node in the tree used in the proof of Theorem 26.1 in section 26.2 can be represented by a picture in the style of Figure 26-1. How many such nodes will there be in the tree?

26.6Prove Konig’s¨ lemma directly, that is, without using the compactness theorem, by considering the subtree T * of T consisting of all nodes that have infinitely many nodes above them (where above means either immediately above, or immediately above something immediately above, or . . . ).