











Title 


Speaker 
백진언



Date 
20180910 


Host 



Place 
KAIST 




Abstract : The infamous ErdősSzekeres conjecture, posed in 1935, states that the minimum number ES(n) of points on a plane in general position (that is, no three colinear points) that guarantees a subset of n points in convex position is equal to 2(n2) + 1. Despite many years of effort, the upper bound of ES(n) had not been better than O(4n – o(n)) until Suk proved the groundbreaking result ES(n)≤2n+o(n) in 2016.
In this talk, we focus on a variant of this problem by Erdős, Tuza and Valtr regarding the number ETV(a, b, n) of points needed to force either an acup, bcap or a convex ngon for varying a, b and n. They showed ETV(a, b, n) > sum_{i=nb}^{a2} binom{n}{i2} by supplying a set of points with no acup, bcap nor a ngon of that many number, and conjectured that the inequality cannot be improved. Due to their construction, the conjecture is in fact equivalent to the ErdősSzekeres conjecture. However, even the simplest equality ETV(4, n, n) = binom{n+1}{2} + 1, which must be true if the ErdősSzekeres conjecture is, has not been verified yet. To the best of our knowledge, the bound ETV(4, n, n) ≤ binom{n + 2}{2} – 1, mentioned by Balko and Valtr in 2015, is currently the best bound known in literature.
The talk is divided into two parts. First, we introduce the mentioned works on the ErdősSzekeres conjecture and observe that the argument of Suk can be directly adapted to prove an improved bound of ETV(a, n, n). Then we show the bound ETV(4, n, n) ≤ binom{n+2}{2} – C sqrt{n} for a fixed constant C>0, improving the previously known best bound of Balko and Valtr. 





