기초과학VOD

BASIC SCI VOD

  •   >  
  • 연구동향
  •   >  
  • 기초과학VOD
Super Title 2018 Discrete Math 세미나
Title On the off-diagonal Erdős-Szekeres convex polygon problem
Speaker 백진언  (  NIMS  ) Date 2018-09-10
Host KAIST Place KAIST
VOD    
The infamous Erdős-Szekeres 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(n-2) + 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 a-cup, b-cap or a convex n-gon for varying a, b and n. They showed ETV(a, b, n) > \sum_{i=n-b}^{a-2} \binom{n}{i-2} by supplying a set of points with no a-cup, b-cap nor a n-gon 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ős-Szekeres conjecture. However, even the simplest equality ETV(4, n, n) = \binom{n+1}{2} + 1, which must be true if the Erdős-Szekeres 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ős-Szekeres 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.

이 페이지에서 제공하는 정보에 만족하십니까?