In 1932 a problem was posed to a very talented but not-yet famous group of young mathematicians. Among a couple others, the group consisted of Eszther Klein, George Szekeres, and Paul Erdős. Erdős, for instance, was 19 at the time. The problem was this:
Show that for any , there is a smallest integer such that every set of at least points in the plane (with no three collinear) contains an -subset forming a convex -gon.
Erdős and Szekeres are credited with proving it (in several different ways), but from the endeavor Eszther and Szekeres started to date, and few years later got married. For this reason, Erdős called the result the Happy Ending Theorem. How cute. Let’s prove it.
First let’s make sure we understand all the adjectives and nouns in the statement. A convex polygon is one that never “caves in”. Here are some examples. Those on the left are convex, those on the right are concave.
Ok, so what we want is to see that given any set of points in the plane, can we find of the them which form a convex -sided polygon (i.e. a convex -gon). And the only silly case to throw out is if there are three in a line, because clearly those do nothing for us. For instance, with this random set 10 points,
we are able to find a convex 6-gon. Such as this one
But is 10 always enough to find six that form such a shape? Or maybe 10 is enough to always find a convex 7-gon? Let’s do a quick example with the 4-gon, better known by 7th graders a quadrilateral. It’s easy to find examples of four points which form a concave 4-gon. Let’s show that given any 5 points in the plane (no 3 colinear) we can find four of them that form a convex -gon. The first step is to find what is called the convex hull of the points.
The convex hull is the smallest convex polygon containing all the points. It’s like if the points are pegs and you wrapped a string around all the points and pulled it taut. The important thing to note is that (thankfully) the convex haul is convex. But it’s pretty intuitive when you see it. The convex hull of our previous example is this
Ok, so getting back to trying to show that our 5 points contain a convex -gon: after taking the convex hull observe that the hull can take one of three shapes: either a pentagon, a quadrilateral with one interior point, or a triangle with two interior points.
In each of the first two cases there is clearly a convex 4-gon. So what about that last one? You’d expect it to be true, but how do we prove it? I’ll give the proof that was given to me when I first saw this. (There are several pretty straightforward ones). Recalling from when you learned this back in the 90’s, a triangle can always be divided up like this:
And now it is easy to run through the cases in your head and check that no matter how we place the points in these sectors, we always get a convex 4-gon.
Therefore 5 is the smallest number needed to guarantee that a subset of four of these vertices forms a convex 4-gon. So that wasn’t so bad. But this sort of argument might get pretty complicated with large numbers. And since I’m blogging about this result, the proof certainly isn’t that boring. But more importantly, there is no reason to think that this argument would extend to proving the existence of convex (really big)-gons. And therefore, who’s to say that there isn’t a clever way to arrange infinitely many points such that a convex -gon is somehow avoided completely? The answer to this question is: us. We’re to say. Right now. And here it goes.
Proof. We want to find points that form a convex -gon from a set of points. First, assume that the points have the following property: “For any subet of the points of size 4, those four points form a convex 4-gon.” i.e. it is impossible to create a concave 4-gon out of the points. We first show that if they have this property, then we’re done. That somehow we can extend this very much local condition on small subsets of , to a global statement on the complete set.
We do it by contradiction. Assume that we have points with this property but which do not form a convex -gon. Then in particular the convex hull (which forms a convex polygon) can not be of size . i.e. some of the points must be contained inside the hull like in our example above. Say the hull is a -gon with and there are points inside the hull.
Now triangulate the -gon in any way. We know that there is at least one point within the -gon and this point can not lie on any of the internal line sigments, else it would be colinear with two others, which we assumed it was not. Therefore it must lie within one of the triangles.
But this is a contradiction since it and the the three vertices of the triangle that contain it do not form a convex 4-gon.
Recall from last time that we proved that there exists a number which is the smallest number such that any 2-coloring (say red and blue) of the -uniform hypergraph on vertices contains either a red -uniform complete hypergraph on vertices or a blue -uniform complete hypergraph on vertices.
Now set . Given points in the plane, color each 4-set by convexity. i.e. color a set of four vertices red if it determines a convex 4-gon and blue if it determines a concave 4-gon.
Then thinking about our points as vertices and the 4-sets as hyperedges of size 4, what we are doing is actually coloring the edges of a 4-uniform complete hypergraph on vertices! Cool! So let’s see what we get from that. By the definition of , we are guaranteed that there is either a set of vertices all of whose sets are red, or vertices all of whose 4 sets are blue.
But wait! Our example told us that given any 5 points in the plane, we can always find a convex 4-gon. So it’s impossible to have points all of whose 4-subsets are colored blue! So it can’t be the second option, therefore it must be the first: there must be points all of whose four subsets are colored red. Which means that we have points whose 4-sets are all convex. Which we just showed implies that the points must form a convex -gon. Done!
Pretty cool, huh? And it shows the brilliance of Erdős and Szekeres because they did not know of this Ramsey theory result when they proved it this way. They had to have the insight that not only was this a clever way to attack to problem, but also that such a Ramsey theory result is true and sufficient. So what did you do when you were 19? :-)