[Mittagsseminar TI] Fwd: [i-prof] [i-studi] Invitation Master's thesis defense

[László Kozma <laszlo.kozma@fu-berlin.de>]

Reminder: this thesis defense is in today's noon seminar.


-------- Forwarded Message --------
Subject: [i-prof] [i-studi] Invitation Master's thesis defense
Date: Thu, 9 Nov 2023 12:09:54 +0100
From: Fang Lin <fangl94@zedat.fu-berlin.de>

Dear all,

I hereby invite you to the upcoming defense of my master's thesis, titled
"On Erdős-Szekeres Problem".

The defense will be held in room SR051 (Takustraße 9) on Tuesday, November
14th, 2023 at 12:00, and will be held in English.

Advisor and first reviewer: Prof. Dr. László Kozma
Second reviewer: Dr. rer. nat. Katharina Klost

Best regards，
Fang Lin

Abstract:
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) <=
\binom{2n-4}{n-2}+1 = 4^{n-o(n)}, while in 1961, they confirmed that 
N(n)>= 2^{n-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  4^{n-o(n)}. A noteworthy development occurred
in 2016 when Andrew Suk improved the upper bound to 2^{n +o(n)}. The best
upper bound till today is 2^{n +O(\sqrt{nlogn)}}.

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.