Introduction to Ramsey Theory: Lecture notes for undergraduate course

Consider the following configuration:

This is a \((4,4,2)\) configuration. As we already know, the eight points in the (4,4) part of the given configuration do not contain a convex pentagon.

Suppose that there is a convex hexagon in this configuration. Then the hexagon has to contains both green points inside of the blue quadrilateral. (If the convex hexagon contains only one green point then the remaining five points belong to the set of red and blue points, which contradicts the fact that those points do not contain a convex pentagon.)

Since the line determined by the two green points divides the plane in the way that each of the two half-planes contains only two red and two blue points, the convex hexagon must have two red, two blue, and two green vertices. But this hexagon is not convex because the blue points are inside of the quadrilateral determined by the red and green points. See Figure 6.5.3.

If the given five points are vertices of a convex pentagon then any four points form and empty convex quadrilateral.

By Esther Klein's result we know that any five points in the plane in general position contain convex quadrilateral, Say that the given five points \(S\) do not determine a convex pentagon. Then the convex hull of the set \(S\) has three or four points. In both cases there is an empty convex quadrilateral. See Figure 6.5.5

Let \(S\) be a set of \(n\) points in the plane in general position, with \(n\geq 6\text{.}\) Let

be the set of all lines in the plane determined by pairs of points from the set \(S\text{.}\) Let \(p\) be a line that is not parallel to any line from the set \(L\) and such that all points that belong to the set \(S\) are on the same side of \(p\text{.}\) (In other words, none of the line segments with the end points from \(S\) intersects the line \(p\text{.}\))

Move the line \(p\) towards the set \(S\text{.}\) Let \(p'\) be the line that contains a point from \(S\text{,}\) that is parallel to the line \(p\) and that there is no element form \(S\) between lines \(p\) and \(p'\text{.}\) (See Figure 6.5.6.)

Continue moving the line \(p\) till it reaches five points from \(S\text{.}\) (See Figure 6.5.7.)

What should we do next?

The base case is trivial.

Suppose that the claim is true for some fixed \(n\geq 4\text{,}\) i.e. suppose that \(n\geq 4\) is such that any \(n\) points in the plane in general position form a convex polygon if and only if every four of them form a convex quadrilateral.

Let \(S\) be the set of \(n+1\) points in the plane in the general position. If the points from \(S\) form a convex \((n+1)\)-gon then any four points from \(S\) are vertices on that convex polygon and thus form a convex quadrilateral.

Suppose that any four points from \(S\) form a convex quadrilateral. We note that by the inductive hypothesis this means that any \(n\) points from \(S\) form a convex \(n\)-gon.

Let \(\overline{S}\) be the convex hull of \(S\text{.}\) The \(|\overline{S}|=n+1\) or \(|\overline{S}|=n\text{.}\) (Is it possible that \(|\overline{S}|\lt n\text{?}\) Why?)

If \(|\overline{S}|=n+1\) then \(S=\overline{S}\) and \(S\) is convex \((n+1)\)-gon.

Let \(|\overline{S}|=n\text{.}\) Then the point \(A\) such that \(\{A\}=S\backslash \overline{S}\) is inside the \(n\)-gon determined by the points from \(\overline{S}\text{.}\) Let \(X\in \overline{S}\) and consider the line through the points \(A\) and \(X\text{.}\) This line intersects the line segment with the endpoints \(Y,Z\in S\text{.}\) See Figure 6.5.9.

Observe that the quadrilateral determined by the points \(A\text{,}\) \(X\text{,}\) \(Y\text{,}\) and \(Z\) is not convex which contradicts our assumption that any four points from \(S\) form a convex quadrilateral.

Hence \(|\overline{S}|=n+1\) and \(S\) is a convex \((n+1)\)-gon, which completes the inductive step.

By Ramsey's theorem there is a set \(T\text{,}\) \(T\subset S\text{,}\) and \(|T|=n\text{,}\) such that for any \(i,j,k\in T\text{,}\) \(i\lt j\lt k\text{,}\) the set \(\{i,j,k\}\) is always of the same colour, say blue. But this implies that any four points from \(T\) form a convex quadrilateral. To see this take \(x,y,z,w\in T\) and suppose that \(x,y,z\text{,}\) and \(w\) determine a concave quadrilateral. Suppose that the point \(w\) is inside of the triangle determined by \(x,y\text{,}\) and \(z\text{.}\) Also, suppose that \(x\lt y\lt z\text{.}\)

We consider four cases given on Figure 6.5.12:

We take the following facts as given:

1. \(\displaystyle f(k,l)=f(l,k)\)

2. From

   \begin{equation*} f(k,l)\leq \binom{k+l-4}{k-2}+1 \end{equation*}

   it follows that \(f(4,4)\leq7\text{,}\) \(f(5,4)\leq11\text{,}\) and \(f(5,5)\leq 21\text{.}\)

3. \(f(k,3)=f(3,k)=k\text{.}\)

Consider the set \(S\) of 6 points in the plane in general position given on Figure 6.5.14.

Note that there is NO a 4-cup or a 4-cap in this configuration. Hence \(f(4,4)\geq 7\text{,}\) which implies that \(f(4,4)=7\text{.}\)

Next we consider a configuration of 6 points with no 4-cup or 4-cap, like one above. We call this configuration \(A\text{.}\) Let \(B\) be a 4-cup. We place the configurations \(A\) and \(B\) in the way that the following conditions are satisfied:

1. Every point in \(B\) has greater first coordinate than the first coordinates of any point in \(A\text{.}\)

2. The slope of any line connecting a point in \(A\) with a point in \(B\) is greater than the slope of any line connecting two points in the same configuration.

Let \(S=A\cup B\text{.}\) See Figure 6.5.15.

Also note

1. Any cup in \(S\) that contains both points from \(A\) and \(B\) can contain only ONE point from \(B\text{.}\) (Why?)

2. Therefore the configuration \(S\) can contain at most a \(4\)-cup.

3. The configuration \(S\) does not contain a \(4\) cap. (Why?)

Hence, the configuration \(S\) contains neither a \(5\)-cap nor a \(4\)-cap. It follows that

Thus, \(f(5,4)=f(4,5)=11\text{.}\)

Finally we consider two configurations, \(X\) and \(Y\text{,}\) that satisfy the following conditions:

1. \(|X|=|Y|=10\text{.}\)

2. The configuration \(X\) does not contain a \(4\)-cap or a \(5\)-cap. This is possible because \(10\lt f(4,5)\text{.}\)

3. The configuration \(Y\) does not contains a 5-cup or a 4-cap. This is possible because \(10\lt f(5,4)\text{.}\)

4. Every point in \(Y\) has greater first coordinate than the first coordinates of any point in \(X\text{.}\)

5. The slope of any line connecting a point in \(X\) with a point in \(Y\) is greater than the slope of any line connecting two points in the same configuration.

Let \(Z=X\cup Y\text{.}\) See Figure 6.5.16.

Also note

1. Any cup in \(Z\) that contains both points from \(X\) and \(Y\) can contain only ONE point from \(Y\text{.}\) (Why?)

2. Therefore the configuration \(Z\) can contain at most a \(4\)-cup.

3. Any cap in \(Z\) that contains both points from \(X\) and \(Y\) can contain only ONE point from \(X\text{.}\) (Why?)

4. The configuration \(Z\) can contain at most a \(4\)-cap. (Why?)

Hence, the configuration \(S\) contains neither a \(5\)-cap nor a \(5\)-cap. It follows that

Thus, \(f(5,5)=21\text{.}\)