Scatter enough points and a convex polygon appears whether you want one or not
In Budapest in the early 1930s a group of young mathematicians met in parks and coffee houses to trade problems. One of them, Esther Klein, noticed something and challenged the others to prove it: scatter five points on a page so that no three lie on a line, and you will always be able to pick four of them that form a convex quadrilateral — a four-sided figure with no dent in it. Try as you like to arrange the five points to prevent it. You cannot.
George Szekeres solved it. Paul Erdős generalised it on the spot: for every n, is there a number of points that forces a convex n-gon? There is, and the smallest such number is written ES(n). Erdős later named the whole thing the happy ending problem, because Klein and Szekeres married in 1937 and stayed married for sixty-eight years, dying within an hour of each other.
The claim is not that a convex quadrilateral is likely. It is that one is unavoidable. Below, five points are yours to move; the demo searches every subset on every frame and outlines the largest one in convex position. The outline never drops below four vertices, whatever you do to the points — as long as no three of them line up.
A convex 4-gon is on the board — 3 different subsets of size 4 sit in convex position.
Every pointer move re-runs a brute-force sweep over all 2⁵ subsets, keeping the largest whose convex hull uses all of its own points. That is the definition of convex position, checked directly rather than inferred.
Try it: Start with five and spend a moment trying to get the readout down to 3. Then add points and hunt for a convex pentagon. Load Eight, no pentagon to see one of the rare configurations that dodges it — two nested quadrilaterals — and then drag any point a little. The pentagon appears almost immediately, which is why eight is the last number that can escape and nine cannot.
Klein’s proof takes about four lines and no machinery at all. Take the convex hull of the five points — the shape a rubber band snaps into around them. In general position it has 5, 4 or 3 vertices, and that is the entire case list. Two of the cases hand you the answer immediately. The third needs one idea: a line through the two interior points cannot separate all three triangle vertices from each other, so two of them end up on the same side.
If every point is a vertex of the hull, the five of them already form a convex pentagon. Delete any one and the remaining four are still in convex position. There is nothing to prove and five choices of quadrilateral.
Those are all the cases: the convex hull of five points in general position has 5, 4 or 3 vertices, and each one produces a convex quadrilateral. Four points do not suffice — put one inside the triangle of the other three and no convex quadrilateral exists — so ES(4) is exactly 5.
Try it: Step to the third case and follow the amber line. It enters the triangle through one edge and leaves through another, so exactly one vertex is cut off — leaving two on the far side to pair with the two interior points.
ES(3) = 3 is a definition. ES(4) = 5 is Klein’s observation. ES(5) = 9 was settled in the 1930s by Endre Makai. ES(6) = 17 took until 2006, when George Szekeres — then in his nineties — and Lindsay Peters ran an exhaustive computer search over configurations of sixteen points. That is the complete list. Nobody knows ES(7), and the numbers 3, 5, 9, 17 make the pattern hard to resist: 2ⁿ⁻² + 1.
ES(6) = 17 — Settled in 2006 by George Szekeres and Lindsay Peters, with an exhaustive computer search that took hundreds of hours of CPU time. It remains the last value anyone has determined.
The conjecture ES(n) = 2ⁿ⁻² + 1 matches all four known values, and the lower half of it is a theorem: Erdős and Szekeres built, in 1961, a set of 2ⁿ⁻² points with no convex n-gon. Only the upper half is open. In 2016 Andrew Suk proved ES(n) ≤ 2ⁿ⁺ᵒ⁽ⁿ⁾, which settles the exponential rate — the base is 2 and not something larger — but the o(n) in the exponent is large enough that the bound does not beat the 2005 binomial until n is far past anything drawn here, so it is not plotted.
Try it: Click along the axis. The four solid dots are everything anyone has proven exactly; every hollow dot is a guess that happens to be a proven lower bound. At n = 10 the conjecture says 257 and the best explicit theorem still allows anything up to 6,436.
The 1935 paper does not argue about polygons directly. It sorts the points left to right and looks for two shapes: a cup, a run of points whose slopes keep increasing, and a cap, a run whose slopes keep decreasing. Both are automatically in convex position. The key lemma is a recursion — a set with no a-cup and no b-cap has at most C(a+b−4, a−2) points — and setting a = b = n gives ES(n) ≤ C(2n−4, n−2) + 1.
That binomial coefficient should look familiar. It is the same one Erdős and Szekeres used, in the same paper, to bound the diagonal Ramsey number by 4ᵏ. The geometry and the edge-colouring problem are two readings of one counting argument.
No 4-cup and no 4-cap, so this set can hold at most 6 points. It holds 6. That is extremal — one more point and a longer chain is forced.
| a\b | 2 | 3 | 4 | 5 | 6 |
| 2 | 2 | 2 | 2 | 2 | 2 |
| 3 | 2 | 3 | 4 | 5 | 6 |
| 4 | 2 | 4 | 7 | 11 | 16 |
| 5 | 2 | 5 | 11 | 21 | 36 |
| 6 | 2 | 6 | 16 | 36 | 71 |
The recursion is the whole proof. A set with no a-cup and no b-cap has at most f(a,b) − 1 = C(a+b−4, a−2) points, because you can split the points by whether they end a long cup or a long cap. An n-cup and an n-cap are both in convex position, so f(n,n) points force a convex n-gon: ES(n) ≤ C(2n−4, n−2) + 1. That is the 1935 bound, and it is the same binomial coefficient that Erdős and Szekeres used the same year to prove R(k,k) < 4ᵏ.
Try it: The Extremal six preset has no 4-cup and no 4-cap, which is the most points that is possible — f(4,4) = 7. Click anywhere on the plot to drop a seventh point and watch one of the two chains jump to length 4. It happens wherever you click.
The binomial upper bound is roughly 4ⁿ, and the conjecture says the truth is 2ⁿ — a gap of an exponential factor, untouched except for lower-order improvements for eighty years. In 2016 Andrew Suk proved ES(n) ≤ 2ⁿ⁺ᵒ⁽ⁿ⁾, which pins the exponential rate at exactly 2 and leaves only the o(n) correction and the additive constant in dispute. It is the same shape of result as the 2023 assault on 4ᵏ: a base that had not moved for decades, finally moving. And it is worth being precise about what is still open — the conjecture ES(n) = 2ⁿ⁻² + 1 asks for the exact value, and no value has been determined since 2006.