An End to the Happy Ending Problem

Andrew Suk just placed on arXiv a paper with an almost tight bound for the happy ending problem. These are exciting news for discrete geometers! I’ll use the opportunity to describe the problem and its non-technical history.

Asuk3172270-Anonymous-Statue-0
Andrew Suk and the Anonymous statue.

In the early 1930’s in Budapest, several students used to regularly meet on Sundays in a specific city park bench. This was the bench next to the statue of Anonymous, the first medieval Hungarian chronicler. Among these students were Paul Erdős, George Szekeres, and Esther Klein.

On one such Sunday meeting, Klein pointed out that for any set of five points with no three on a line, four of the points are the vertices of a convex quadrilateral. This easy observation can be proved by considering the convex hull of the five points. If at least four of the points are on the boundary of the convex hull, then we are done. If the convex hull consists only of three of the points, then we consider the line \ell  that passes through the two interior points. We take the two interior points and the two points that are on the same side of \ell  .

FivePointsES

The Budapest students started to think about whether there exists an n  such that every set of n  points with no three on a line contains the vertices of a convex pentagon. More generally, does a similar condition hold for every convex k  -gon? The first to prove the claim was Szekeres. A couple of years later, Esther Klein, who suggested the problem married George Szekeres who solved it. Since then, this problem is called the happy ending problem. They lived together up to their 90’s.

george_esther

For every integer m \ge 3  , let N(m)  denote the smallest integer such that any set of N(m)  points with no three on a line contains a subset of m  points that are the vertices of a convex m  -gon. Erdős and Szekeres published a paper on the problem in 1935. They proved that

2^{m-2}+1 \le N(m) \le \binom{2m-4}{m-2}+1.

Erdős and Szekeres conjectured that N(m)=2^{m-2}+1  , and this is sometimes called “the Erdős–Szekeres conjecture”. Erdős offered a 500$ ` for proving or disproving this conjecture, and a few years ago Ron Graham (who is handling Erdős’ problem awards) increased the amount to 1000$. So far the conjecture was verified up to m=6  by a computer. Over the years several improved bounds were published, but the improvements were always sub-exponential. That is, the value of N(m)  remained between 2^m  and 4^m  (ignoring sub-exponential factors). In his new paper, Suk derives the impressive bound N(m)\le 2^{m+4m^{4/5}}  , settling the problem up to sub-exponential factors. Surprisingly, after 81 years of small progress, Suk’s impressive improvement requires a short proof that does not seem to rely on any kind of heavy machinery.

Advertisements