In the early 1930s a group of bright university students held gatherings in Budapest to discuss math. Among them was Paul Erdős, an eccentric prodigy who would go on to become the most prolific mathematician in history. Other attendees included mathematicians George Szekeres and Esther Klein. One day Klein presented a puzzle to her friends: a deceptively simple question about dots scattered across a page. Unbeknownst to them, the puzzle would help launch a profound branch of modern math about order among chaos and spark a romance that would last the rest of Klein’s life.
Here’s what Klein presented to her pals: speckle five dots on a page wherever you like, as long as no three dots fall along the same straight line. Will four of those dots always form the corners of a four-sided shape with no dents or crossed sides? In mathematical terms, must some four of the five dots form a convex quadrilateral?
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
With only four dots, it’s clearer to see that a convex quadrilateral might elude you, depending on where the dots fall. But the five-dot case changes things.
Grab a pencil and test it for yourself. Place five dots at random, with no three dots in the same line, and hunt for the four-cornered dentless shape. Then try to be clever by attempting to intentionally arrange the dots to deny yourself such a shape. You will fail every time. No matter how you place five dots, four of them will always form a convex quadrilateral. Klein proved this with an elegant argument.
Imagine that the dots protrude from the page to form pegs. If you stretch a rubber band around all of the pegs and let it snap taut against the outermost ones, it will trace a convex boundary because rubber bands don’t form spontaneous dents. There are three cases to consider: the band touches five pegs; the band touches four pegs with one trapped inside; or the band touches three pegs with two trapped inside. It can’t touch only two pegs unless all five lie in a straight line, which the rules forbid. If the band touches four pegs, then we’ve already found our convex quadrilateral (four sides) made of those four boundary points. If it touches five pegs, forming a convex pentagon, then you can lift the band off of any one of the pegs, and it will snap to the remaining four to form a convex quadrilateral. The tricky case occurs when the band touches only three points, forming a triangle with two interior points.
Does this three-point configuration always admit a convex quadrilateral? It does. Draw a straight line through the two interior points and extend it across the page. That line slices the plane into two halves, one of which will contain two corners of the outer triangle (the bottom half in the figure below). Those two corners together with the two interior dots always form a convex quadrilateral. Why? For four dots, the only way to fail is if one is trapped inside the other three, unable to participate in the boundary. But none of these four dots can get trapped. The two triangle corners are among the farthest-out points of the whole cluster, so nothing can box them in. And if you take those two corners and form a triangle with either of the other dots, you’ll notice the fourth dot always sits outside of it, unenclosed.
After impressing her friends with this puzzle and its neat resolution, Klein did what mathematicians do: she wondered how it generalizes. How many points would you need to guarantee, say, a convex pentagon, a convex hexagon or a convex 100-gon? Or perhaps, for these larger shapes, no amount of points would be guaranteed to produce them. Could it be that you could arrange any number of points while avoiding the creation of a convex hexagon?
Erdős and Szekeres settled part of the mystery in 1935. They proved that, for any number of sides you choose, some finite number of points is always enough to ensure that shape: gather that amount of dots, with no three in a line, and a convex polygon of that size is guaranteed. Enough dots will force a convex hexagon. The same goes for a convex 100-gon—you just need more dots. With the correct number of dots, no arrangement, however cunning, can dodge these shapes forever.
Erdős dubbed this the “happy ending problem” because, somewhere in the course of trading geometric drawings, Esther Klein and George Szekeres fell in love. They married in 1937 and enjoyed a storied life together. As a Jewish couple facing the rise of Nazi persecution in Europe, they fled, spending the war years as refugees in Shanghai, where their first child was born. In 1948 they resettled in Australia and built a life steeped in math: Szekeres worked as a professor and became president of the Australian Mathematical Society while Klein taught math at Macquarie University and ran extracurricular sessions where she posed geometric problems for students, just as she had done with her friends in her youth.
The legacy of the happy ending problem extends beyond romance. It helped seed an active branch of modern math known as Ramsey theory. While writing their paper, Erdős and Szekeres discovered a theorem from the young British polymath Frank Ramsey, who had already done groundbreaking work in philosophy, economics and math by his untimely death at age 26. Ramsey wrote in more abstract terms, but his celebrated theorem is best imagined as a cocktail party where some attendees are acquaintances and some are strangers: For a suitably large party, will there always be some group of people who are either all mutual acquaintances or all mutual strangers? Ramsey proved that, yes, with enough invitees, it becomes impossible to handcraft a guest list that avoids cliques of acquaintances or strangers. To ensure a bigger clique, you simply need a bigger party.
How much bigger is a thornier question that remains open today, but Erdős was the first person to make significant progress on it. Ramsey’s theorem and the happy ending problem share a common insight: once systems grow large enough, pockets of order become unavoidable. That’s the central thread of Ramsey theory. You can scatter points or invite guests as haphazardly as you want, and yet tidily arranged clusters will still emerge. It’s a vibrant branch of research with roots reaching into many disparate areas of math. Erdős was the central figure in the field throughout his career, and his work on the happy ending problem helped kick that off.
Ramsey theory is profound, but it comes with a signature frustration. Proofs in the field tend to guarantee that order must appear somewhere at some point without revealing where it hides or exactly how large a structure must grow to guarantee it. For the happy ending problem, Klein showed that five points guarantee a quadrilateral, and Erdős and Szekeres reported that nine points necessitate a pentagon but eight can still avoid one; concrete quantifications stalled there for 70 years. Not until 2006 was the next number found, and it was found by a familiar name. Szekeres, still circling the problem that had introduced him to his wife more than seven decades earlier, teamed up with Lindsay Peters and marshaled an extensive computer search to confirm that 17 points necessitate a convex hexagon, while 16 can still avoid one. The paper was published posthumously, after Szekeres’s death.
The discovery matched a conjecture that Erdős and Szekeres had put forth as young men. They predicted that 2(n − 2) + 1 points is the minimum needed to force an n-sided convex polygon. The quadrilateral, pentagonal and hexagonal cases all obey this formula, but no larger shapes have been confirmed. Erdős left behind a $500 cash prize to anyone who proves that it holds in general. The prize remains unclaimed, although in 2016 mathematician Andrew Suk came tantalizingly close.
Klein and Szekeres both died in 2005 within an hour of each other. They left behind two children and a mathematical legacy worthy of the name “Happy Ending.”