Introduction to Ramsey Theory: Lecture notes for undergraduate course

We already know that \(N(3)=3\text{,}\) \(N(4)=5\text{,}\) and \(N(5)=9\text{.}\)

Let \(n\geq 4\text{.}\) Let \(m>R(4;n,5)\) and let \(S_m\) be a set of \(m\) points in the plane in general position. Let

i.e., let \(S_m^{(4)}\) be the set of all four-element subsets of \(S_m\text{.}\)

We define a 2-colouring

in the following way. For \(T\in S_m^{(4)}\)

See Figure 6.2.5.

By Ramsey's theorem (and our choice of \(m>R(4;n,5)\)) there is an \(n\)-element set \(\Delta_n\subset S_m\) such that all of its four-element subsets are coloured blue or a \(5\)-element set \(\Delta_5\subset S_m\) such that all of its four-element subsets are coloured red.

Since \(N(4)=5\text{,}\) any set of five points in the plane in general position contains a convex quadrilateral. This implies that it is impossible to find a \(5\)-element set \(\Delta_5\subset S_m\) such that all of its four-element subsets are coloured red.

Hence there must be an \(n\)-element set \(\Delta_n\subset S_m\) such that all of its four-element subsets are coloured blue. But then, by Lemma, the set \(\Delta_n\) forms a convex \(n\)-gon.

We prove the theorem by induction on \(m=k+l\) if \(m\geq 6\text{.}\)

1. Base Case: For any \(k\geq 3\text{,}\)

   \begin{equation*} f(k,3)=f(3,k)=k\text{.} \end{equation*}

   Take a set \(S\) with \(k\) points in the plane in general position. Let

   \begin{equation*} S=\{ A_1,A_2,\ldots, A_k\} \end{equation*}

   where for \(i\lt j\text{,}\) the \(x\)-coordinate of \(A_i\) is less than the the \(x\)-coordinate of \(A_j\text{.}\)

   Let \(s_i\) be the slope of the line segment \(\overline{A_iA_{i+1}}\text{,}\) for \(i\in [1,k-1]\text{.}\) If

   \begin{equation*} s_1\lt s_2\lt \cdots \lt s_{k-1} \end{equation*}

   then \(S\) contains a \(k\)-cup.

   If, for some \(i\in [1,k-2]\text{,}\)

   \begin{equation*} s_i>s_{i+1} \end{equation*}

   then the set \(S\) contains a 3-cap \(\{A_i,A_{i+1},A_{i+2}\}\text{.}\)

   

2. Note that we have proved that \(f(3,3)=3\) and \(f(4,3)=f(3,4)=4\text{.}\) In particular this means that if \(k,l\geq3\) are such that \(k+l\leq 7\) then \(f(k,l)\) exists.

3. Inductive Step: Let \(m\geq 7\) and \(k,l\geq 3\) be such whenever \(k+l=m\) then \(f(k,l)\) exists. We choose \(k,l\geq 3\) such that

   \begin{equation*} k+l=m+1\text{.} \end{equation*}

   This implies that

   \begin{equation*} (k-1)+l=k+(l-1)=m \end{equation*}

   and, hence \(f(k-1,l)\) and \(f(k,l-1)\) exist.

   Let

   \begin{equation*} n=f(k-1,l)+f(k,l-1)-1\text{.} \end{equation*}

   Let us fix a set \(S\) of cardinality \(n\) and any right for \(S\) system of coordinates. We have to prove that \(S\) contains either a \(k\)-cup or an \(l\)-cap. Let \(L\) be the set of all points that are the left ends of \((k-1)\)-cups in \(S\text{.}\)

   

   1. Let us assume first that the set \(S\backslash L\) has at least \(f(k-1, l)\) points. Then it contains either a \((k-1)\)-cup or an \(l\)-cap. But taking the set \(L\) out of \(S\) destroys all \((k-1)\)-cups in \(S\text{.}\) Hence \(S\backslash L\) does not contain any \((k-1)\)-cups and therefore must contain an \(l\)-cap.

   2. Suppose then that \(|S\backslash L| \leq f(k-1, l) -1\text{.}\) It follows

      \begin{equation*} |L| = |S| - |S\backslash L| \geq n - f(k-1, l) + 1 = f(k, l-1)\text{.} \end{equation*}

      Therefore, there exists a \(k\)-cup in \(L\) (and everything is alright) or there exists a \((l-1)\)-cap in \(L\text{.}\)

      Let us consider the point \(Y\text{,}\) the right end of that cap.

      Let \(X\) be the point that is immediately to the left of \(Y\) in the \((l-1)\)-cap in \(L\text{.}\) Since \(Y\in L\text{,}\) the point \(Y\) is a left end of some (\(k-1)\)-cup in \(S\text{.}\)

      Let \(Z\) be the point that is immediately to the right of \(Y\) in the \((k-1)\)-cup in \(S\text{.}\) If

      \begin{equation*} \text{ Slope of } \overline{XY}>\text{ Slope of } \overline{YZ} \end{equation*}

      then adding the point \(Z\) to the \((l-1)\)-cap in \(L\) makes an \(l\)-cap in \(S\text{.}\) (See Figure 6.2.16.)

      

      If

      \begin{equation*} \text{ Slope of } \overline{XY}\lt \text{ Slope of } \overline{YZ} \end{equation*}

      then adding the point \(X\) to the \((k-1)\)-cup in \(S\) makes an \(k\)-cup in \(S\text{.}\) (See Figure 6.2.17.)

      

      Therefore, any set \(S\) such that

      \begin{equation*} |S|=n=f(k-1,l)+f(k,l-1)-1 \end{equation*}

      contains either a \(k\)-cup or an \(l\)-cup which implies that \(f(k,l)\) exists and that

      \begin{equation*} f(k,l)\leq f(k-1,l)+f(k,l-1)-1\text{.} \end{equation*}

   By the Principle of Mathematical Induction, \(f(k,l)\) exists for any \(k,l\geq 3\text{.}\)