The MathNet Korea
Information Center for Mathematical Science

세미나

Information Center for Mathematical Science

세미나

KAIST Discrete Math 세미나
Title Enumerating sets of integers with multiplicative constraints
Date 2018-09-10
Speaker 백진언(NIMS)
Sponsors 2018-09-10
Host KAIST
Place E6-1, Room 1401
Abstract 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.