RT Part 4; The Happy Ending Theorem

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 m \in \mathbb{N}, there is a smallest integer N = N(m) such that every set of at least N points in the plane (with no three collinear) contains an m-subset forming a convex m-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 N points in the plane, can we find m of the them which form a convex m-sided polygon (i.e.  a convex m-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 4-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 4-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 8675309-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 m points that form a convex m-gon from a set of N points.  First, assume that the m points have the following property: “For any subet of the m 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 m, to a global statement on the complete set.

We do it by contradiction. Assume that we have m points with this property but which do not form a convex m-gon.  Then in particular the convex hull (which forms a convex polygon) can not be of size m.  i.e.  some of the points must be contained inside the hull like in our example above.  Say the hull is a t-gon with t < m and there are m-t \geq 1 points inside the hull.

Now triangulate the t-gon in any way.  We know that there is at least one point within the t-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.

So we have shown that (the very strong sounding statement that) if all the 4-subsets of our m points in the plane form a convex 4-gon, then the m points must form a convex m-gon, as desired.

Recall from last time that we proved that there exists a number R(m, 5 ; 4) which is the smallest number such that any 2-coloring (say red and blue) of the 4-uniform hypergraph on R(m, 5 ; 4) vertices contains either a red  4-uniform complete hypergraph on m vertices or a blue 4-uniform complete hypergraph on 5 vertices.

Now set N = R(m, 5 ; 4).  Given N 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 N 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 N = R(m, 5 ; 4) vertices!  Cool!  So let’s see what we get from that.  By the definition of N = R(m, 5 ; 4), we are guaranteed that there is either a set of m vertices all of whose 4 sets are red, or 5 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 5 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 m points all of whose four subsets are colored red.  Which means that we have m points whose 4-sets are all convex.  Which we just showed implies that the m points must form a convex m-gon.  Done!

\square

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?  :-)

Advertisements

About Jay Cummings

I am a fifth year mathematics Ph.D. student at UCSD.
This entry was posted in Ramsey Theory. Bookmark the permalink.

9 Responses to RT Part 4; The Happy Ending Theorem

  1. Z Norwood says:

    #Edit: ‘Erdös’ \mapsto ‘Erdős’.

  2. Z Norwood says:

    WP keeps asking me to approve “Ping-backs”. I don’t know what this means, and clicking on the ‘Approve’ link in the email doesn’t seem to do anything.

  3. Z Norwood says:

    Good post. I particularly enjoyed “(really big)-gons”.

    Your posts have infinitely better pictures than mine & Hotovy’s.

    • JCummings says:

      Thanks! Yeah, constructive proofs in graph theory tend to be pretty visual, for some weird reason. So pictures help. They are a slight pain to make though, so you better be enjoying them! :-)

      Thanks for the Erdős correction! And no, I am not aware of how to fix the very annoying ping backs. I like to be notified when you guys comment on something that I wrote or commented on already. But “approving” comments (whatever that does) and getting notified when I create a link from one of my posts to another one of my posts, is bit much. I’ll try to figure it out, and if you do, let me know.

      Now get going on your second AC post this weekend! I want to read more!

      • Z Norwood says:

        Comment-leavers have to be approved (by you or me) before their comments will show up publicly. But now that we’ve approved Danny, for example, he can leave comments without having to have them approved. I don’t know what this ping-back business is, though.

  4. Z Norwood says:

    Well, I thought the end-of-proof symbol could be made betterly with
    <P ALIGN="right"> $ \square$</P>
    but that appears to have put it on the next line.

    • JCummings says:

      Well the next line is fine with me, I always do that. But it looks like there’s also a line in between, like it started a new paragraph with it.

  5. Pingback: The Invariant Subspace Problem and Lomonosov’s Theorem (Part 1 of 3). | whateversuitsyourboat

  6. Pingback: The Invariant Subspace Problem and Lomonosov’s Theorem. (Part 1 of 3) | Alexander Adam Azzam

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s