menu +

The Happy Ending Problem

Introduction

The Happy Ending problem first manifested itself on a typical wintery evening in 1933. These evenings would witness meetings of the Anonymous society (named so because the meetings happened under the statue of Anonymous in the city park of downtown Budapest, in Hungary), which involved Paul Erdös, Esther Klein, Endre Makai, and György Szekeres. The meetings served to feed their common passion for mathematics, and — as the story goes — a few things besides.

It was during such a meeting that Klein posed the following question after some doodling: how many points do we need on a plane to guarantee that some four of them form a convex quadrilateral? Clearly, four points are not enough: with some bad luck, three of them form a triangle and the fourth lies inside the triangle formed by the other three, and as a result, there are no four points that form a convex quadrilateral. On the other hand, and a little less clearly, five points suffice.

Klien’s reasoning was as follows: if the five points lie on a pentagon, then any four of them form a convex quadrilateral. If four points form a convex quadrilateral with the remaining point in the interior, then we are done again, for the four “outer” points take on the desired shape. Finally, if three points form a triangle and both the remaining points lie in the interior of the triangle, then one of the sides of the triangle together with the line that joins the two interior points will form a convex quadrilateral.

We remark that throughout this discussion, the points are always assumed to be in what is called the general position, which means that no three points are collinear.

 
q l

Klein’s proof for why any set of five points in general position must contain four points that determine a convex quadrilateral.

 
q l

Makai’s extremal example showing 8 points without a convex pentagon.

Makai managed to show that one would need nine points to guarantee the existence of a convex pentagon. Interestingly, there is exactly one configuration of eight points for which a convex pentagon cannot be formed — when the first four points form a square and the last four points form a square surrounding the first. The addition of a new point anywhere causes a convex pentagon. This, with some detail, amounts to a proof of Makai’s claim.

As far as specifics go, the story ends here — nobody knows the exact value of the smallest number of points one would need to guarantee a convex hexagon. What is known, however, is that the number is more than $17$, and less than $37$.

Beyond the specifics, the natural generalization of this question that emerges is the following: given a natural number $n$, how many points do we need before we can guarantee that some subset of $n$ vertices will form a convex polygon? The first thing to ask is whether the answer is even finite for every $n$, and if it is, then one might wonder how the answer behaves as a function of $n$. Notationally, the tradition is to use $g(n)$ to refer to the smallest number of points necessary to guarantee that a subset of $n$ of them will form a convex polygon.

Erdös and Szekeres answered the first question in the affirmative, showing upper bounds in a couple of different ways. The first method appealed to Ramsey theory, and shows that:

$$g(n) \leq R_4(5,n).$$

The other method relies on geometric considerations and leads to:

$$g(n) \leq {2n - 4 \choose n-2} + 1.$$

We will describe a couple of proofs with a Ramsey flavor and then move to the geometric variant. Incidentally, it was Erdös who dubbed this the Happy Ending Problem — considering that shortly after these results were published, Szekeres and Klein got married.

Some Notions and Notation

In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object. The convex hull or convex envelope of a set $X$ of points in the Euclidean plane or Euclidean space is the smallest convex set that contains $X$. For instance, when $X$ is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around $X$. Given a set $S$ of points on the plane, we say that the points determine a convex object if there are no points from $S$ in the interior of the convex hull of $S$.

We use $R(s,t)$ to denote the Ramsey number on $2$-colored complete graphs. That is to say, $n = R(s,t)$ is the smallest integer such that any coloring of $K_n$ with two colors (say red and blue) admits a red $K_s$ or a blue $K_t$. The notion can be generalized in several ways. For instance, we use $n := R_k(s,t)$ to denote the Ramsey number on $2$-colored complete hypergraphs, where we are assured that in any $2$-coloring of the $k$-sized subsets of $K_n$, there is a subset of $[n]$ of size $s$ all of whose $k$-subsets are colored red, or there is a subset of $[n]$ of size $t$ all of whose $k$-subsets are colored blue. On the other hand, we use $n := R(s_1, s_2, \ldots, s_t)$ to denote the Ramsey number on $t$-colored complete graphs. In this case, in any coloring of the edges of $K_n$ with colors from $[t]$, there exists $i$, $1 \leq i \leq t$, for which there is a subset of size $s_i$ colored with color $i$.

We use $[t]$ to denote the set $\{1, 2, \ldots, t\}$.

A few proofs of Erdös-Szekeres

We first show that $g(n) \leq R_4(5,n)$. Suppose we are given some configuration of $N := R_4(5,n)$ points. Label the points arbitrarily from $1, 2, \ldots, N$. We now describe a coloring of the four-subsets of $[N]$. Let $S = \{a,b,c,d\} \subset N$. Consider the points labeled $a, b, c$ and $d$. If these points form a convex quadrilateral in the plane, then color $S$ blue, otherwise, color $S$ red. By definition, we know that $R_4(5,n)$ either has a five-sized subset all of whose $4$-sized subsets are colored red, or it has a $n$ sized set all of whose $4$-subsets are colored blue.

Recall, at this point, Klein’s observation that any set of five points in the plane admits a subset of four points that create a convex quadrilateral. Given this, our coloring certainly cannot admit a five-sized subset all of whose $4$-sized subsets are colored red, for this would mean that we have identified five points in the plan all of whose four-sized subsets do not form convex quadrilaterals, contradicting our observation.

Thus, we must have a subset of size $n$ all of whose four-sized subsets are colored blue, and the corresponding points — by the definition of the coloring — are such that any four points form convex regions in the plane. From here, we claim that the entire set of points form a convex $n$-gon. Notice that it suffices to show that no point lies in the interior of the convex hull of the remaining points. However, this is easy to see, because whenever a point lies in the interior of the convex hull of the remaining points, one can form a triangle enclosing this point, which would then imply a subset of four points that do not form a convex quadrilateral — a contradiction.


There is another elegant proof that uses the Ramsey numbers. This argument is attributed to Tarsy, who was an undergraduate student when he proposed the proof while taking an exam in a combinatorics course.

As before, let suppose we have $N$ points on the plane, and this time, let $N = R_3(n,n)$. We now proceed to color the three-element subsets of $[N]$. Let $S = \{a,b,c\}$ be a 3-element subset where $a < b < c$ (WLOG). Color the set $S$ blue if one encounters the points in the order $(a,b,c)$ by passing clockwise around their convex hull, and color it red otherwise. Since $N$ is $R_3(n,n)$, we are assured of a subset $X$ of size $n$ all of whose $3$-sized subsets are colored with the same color. Now, we claim that the corresponding points form a convex $n$-gon. We will show that any four points among these $n$ form a convex region, and the proof follows as it did in the previous case. We abuse notation and continue to use $X$ to refer to the subset of points on the plane that have labels corresponding to elements in $X$.

Consider any four points from $X$ in the plane, and let $S$ be the subset of $N$ formed by the labels of these points. Recall that, by the choice of $X$, all $3$-sized subsets of $X$ are colored with the same color, and in particular, all $3$-sized subsets of $S$ are colored with the same color as well. Without loss of generality, let the color be blue.

q l

If all triangles of a four-sized subset are monochromatic and the points corresponding to the four-sized subset do not form a convex object, we obtain a contradiction based on the design of the triangles.

Assume, for the sake of contradiction, that one of the points of $S$ lies inside the triangle formed by the other three. Let the endpoints of the triangle be $a, b, c$ with $a < b < c$ (WLOG). Let $d$ be the point on the interior of this triangle. Since $d$ forms a triangle with $a$ and $c$ that is colored blue, so we have $a < d < c$. Now, if $d < b$, then $a < d < b$, and the set corresponding to the triangle $(a,d,b)$ should be colored red, and if $d > b$, then $b < d < c$, and the set corresponding to the triangle $(b,d,c)$ should be colored red. In either situation, we have arrived at a contradiction.


q l

An example of a cap (left) and a cup (right).

We now turn to a proof with a geometric flavor. Let us call a sequence of $n$ line segments consecutive if the right endpoint of the $i^{th}$ line segment is also the left endpoint of the $(i+1)^{th}$, for the $1 \leq i < n$. The length of such a sequence is simply $n$, the number of points that determine the set of line segments. We now propose the following definitions:

A sequence of consecutive line segments is called a cap if their slopes are monotonically decreasing.

A sequence of consecutive line segments is called a cup if their slopes are monotonically increasing.

Now, notice that if we have a cap of length $n$, then the $n$ points involved in the cap actually determine a convex $n$-gon. The same can be said of a cup. So we are naturally interested in knowing if any suitably large set of points either has a cap of length $n$ or a cup of length $n$. Let’s name and conquer: denote by $f(k,l)$ the smallest number of points such that any collection of $f(k,l)$ points on the plane contains a cap of length $k$ or a cup of length $l$. Notice that $g(n) \leq f(n,n)$. We will now focus on showing a bound for $f(k,l)$.

First, observe that $f(k,3) = k$. This is quite easy to see: for example, given any $k$ points $x_1, \ldots, x_k$, if they form a cap of length $k$ then we are done. If not, then the slopes of $(x_1,x_2), \ldots, (x_{k-1},x_k)$ are not monotonically increasing, then there must be a consecutive pair of segments $p, p+1$ for which the slope of $(p+1)$ is less than the slope of $p$, and these two segments form a cup of length $3$, and again, we are done. Along similar lines, one can argue that $f(3,k) = k$. Thus we have:

$$f(k,3) = f(3,k) = k.$$

Now we propose the following recurrence:

$$f(k,l) \leq f(k-1,l) + f(k,l-1) + 1.$$

To show this, consider a collection $X$ of $f(k-1,l) + f(k,l-1) -1$ points in the plane. If some $k$ points form a $k$-cap, the we are done. If not, let ${\mathcal C}$ be the collection of all the $(k-1)$-caps formed by points in $X$.

We are now going to “behead” the caps. Specifically, let $L$ be the set of all the left-most endpoints of caps in ${\mathcal C}$. Consider $X \setminus L$. Now, notice that in $X \setminus L$, even the longest caps have length strictly less than $k-1$. Therefore, if $|X \setminus L| \geq f(k-1,l)$, then $X \setminus L$ must admit a cup of length $l$, and we are done. If, on the other hand, $|X \setminus L| < f(k-1,l)$, then notice that $|L| > f(k,l-1) - 1$, or $|L| \geq f(k,l-1)$. Since we assumed that $X$ does not have caps of length $k$ (recall that if this was the case we would be done straightaway), the set $L$ must admit a cup of length at least $(l-1)$. Now, the points of this cup are actually also the left-most endpoints of $(k-1)$-length caps in $X$.

The final observation that clinches this argument is the following: if a cup of length $(l-1)$ ends at the beginning of a cap of length $(k-1)$, then either the cap or the cup can be extended further, elongating it by one. This is quite easy to see, because if $v$ is the point common to the cap and the cup, and if $u$ lies before $v$ on the cup, and $w$ is next to $v$ on the cap, then depending on the angle between $uv$ and $vw$, the slope from $uv$ to $vw$ is either increasing or decreasing, and either way, either the cap or the cup can be extended by one more, which brings us to the desired conclusion.

 
q l

A cap and a cup combine to form a larger cup (left) or a cap and a cup combine to form a larger cap (right).

 

The recurrence that we established can be opened up so as to arrive at the following:

$$f(k,l) \leq {k+l-2 \choose k-2} + 1.$$

The correctness of the expression above can be verified inductively:

$$f(k,l) \leq f(k-1,l) + f(k,l-1) - 1 \leq {k+l-3 \choose k-3} + {k+l-3 \choose k-2} - 1 = {k+l-2 \choose k-2} + 1$$

The last equality is obtained by applying the simple identity:

$${n+1 \choose k} = {n \choose k } + {n \choose k-1}.$$

Notice that the bound on $g(n)$ comes from setting $k = l = n$.

Schur’s Theorem

An interesting application of Ramsey numbers is in number theory. Consider the following definition. For a number $r$, let $Sr$ the smallest number which satisfies the following property: for any partition of ${1, 2, \ldots, S_r}$ into $n$ parts, there exists a partition containing three numbers satisfying the equation:

$$x + y = z.$$

With our training so far, we are compelled to ask ourselves - does $S_r$ exist, and if it does, what does it look like?

Consider the Ramsey number on $r$-colored graphs: let $t$ be $R(3, 3, \ldots, 3)$. In other words, $t$ is such that in any $r$-coloring of $K_t$, we are assured of the existence of a monochromatic triangle. Ramsey’s theorem tells us that such a $t$ exists, and is finite, for every $r$.

We now claim that the number $t$ is an excellent candidate for $S_n$. That is to say, if we have at least $t$ numbers at hand, then any partition of $[t]$ into $r$ parts will lead to a part with the sum property. Imagine that we want to associate the partitions of $[t]$ with colors of $K_t$, and we would like to engineer the association in such a way that monochromatic triangles start corresponding to the equation $x + y = z$. We urge the reader to ponder for a moment on what a suitable association might be.

To begin with, suppose we are given a partition the numbers $[t]$ into $r$ parts. Let $P_i$ be the numbers in the $i^{th}$ partition. Imagine now $K_t$ to be the complete graph on the vertex set $[t]$, and consider the following coloring of the edges of $K_t$: an edge $(p,q)$ gets color $c_i$ if $(p-q) \in P_i$. Notice that we have used only $r$ colors.

Since we know that every $r$ coloring of $K_t$ admits a monochromatic triangle, our coloring in particular must have one. Let the monochromatic triangle have color $c_j$, and let its end points ${u,v,w}$, with $u < v < w$ (WLOG). Clearly, $(v-u)$, $(w-v)$ and $(w-u)$ lie in $P_j$. Notice that we might set $x$ to $(v-u)$, $y$ to $(w-v)$ and $z$ to $(w-u)$, to achieve the desired effect.

This result was discovered by Issai Schur, a German mathematician of Russian descent in 1916. Schur’s motivation was the study of the the famous equation of Fermat, namely $x^n + y^n = z^n$, restricted to the field of primes. If there are integers $x,y,z$ satisfying this equation, then for every prime $p$, they also solve the congruence equation $x^n + y^n = z^n (mod p)$. Schur used the result above to show that the congruence equation has a non-trivial solution for all large primes $p$, showing that Fermat’s Last Theorem is false in the field $\mathbb{Z}_p$ for any sufficiently large prime $p$.