Springe direkt zu Inhalt

Fang Lin:

On Erdős-Szekeres Problem


The Erdős-Szekeres theorem, established in the 1930s, posits that for a sufficiently large set of points in the plane in general position, it is guaranteed to contain n points forming a convex polygon. In other words, there exists a quantity denoted as N(n) such that any set of N(n) points contains a convex n-gon. This problem is colloquially referred to as the "happy ending problem."

The exact value of N(n) remains elusive, motivating efforts to establish both lower and upper bounds as accurately as possible. Over the course of more than 90 years, extensive research has been dedicated to refining the bounds. For general n, Erdős and Szekeres demonstrated in 1935that N(n) = 2n-1 + 1. Over the course of these 90 years, there have been eight improvements to the original upper bound, albeit the majority of these remain within the limit of 4n-o(n). A noteworthy development occurred in 2016 when Andrew Suk improved the upper bound to 2n +o(n). The best upper bound till today is 2n +O(√n logn).

Recently, a pertinent question has arisen in an article by G.Damasdi et al. concerning the Erdős-Szekeres problem. The question is to determine the smallest value, denoted as S(n), for which a set of S(n) points in general position in the plane does not form a convex n-gon initially, but the addition of any arbitrary point results in the formation of a convex n-gon. This question is of recent origin, with an unestablished upper bound, and it remains unresolved, even in relatively simple cases.

This thesis will commence with an introduction to foundational concepts and provide a historical perspective on the problem's evolution. Subsequently, it will survey the existing upper and lower bounds from the literature concerning the core Erdős-Szekeres problem, along with simpler instances. Following this, the thesis will shift its focus to an investigation of the open question, offering explanations for simple cases and formulating a conjecture regarding its bounds. Finally, it will introduce two interactive tools, namely, the saturation game and the extremal game, both rooted in the Erdős-Szekeres theorem and the open question.

Master of Science (M.Sc.)