KAIST Discrete Math Seminar


Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.
  • Jaehoon Kim, Introduction to Graph Decomposition

    Introduction to Graph Decomposition
    Jaehoon Kim (김재훈)
    Mathematics Institute, University of Warwick, UK
    2018/10/15 5PM
    Graphs are mathematical structures used to model pairwise relations between objects.
    Graph decomposition problems ask to partition the edges of large/dense graphs into small/sparse graphs.
    In this talk, we introduce several famous graph decomposition problems, related puzzles and known results on the problems.
    Tags:
  • JinHoo Ahn (안진후), Mekler’s Construction on NTP1 Theory

    Mekler’s Construction on NTP1 Theory
    JinHoo Ahn (안진후)
    Department of Mathematics, Yonsei University, Seoul
    2018/10/1 Mon 5PM-6PM (E6-1, Room 1401)
    Any structure whose language is finite has a model of graph theory which is bi-interpretable with it. From this idea, Mekler further developed a way of interpreting a model into a group. This Mekler’s construction preserves various model-theoretic properties such as stability, simplicity, and NTP2, thus helps us find new group examples in model theory. In this talk, I will introduce to you what Mekler’s construction is and briefly show that this preserves NTP1.
    Tags:
  • Joonkyung Lee (이준경), The extremal number of subdivisions

    The extremal number of subdivisions
    Joonkyung Lee (이준경)
    Universität Hamburg, Hamburg, Germany
    2018/9/17 Monday 5PM
    One of the cornerstones of extremal graph theory is a result of Füredi, later reproved and given due prominence by Alon, Krivelevich and Sudakov, saying that if H is a bipartite graph with maximum degree r on one side, then there is a constant C such that every graph with n vertices and C n2 – 1/r edges contains a copy of H. This result is tight up to the constant when H contains a copy of Kr,s with s sufficiently large in terms of r. We conjecture that this is essentially the only situation in which Füredi’s result can be tight and prove this conjecture for r = 2. More precisely, we show that if H is a C4-free bipartite graph with maximum degree 2 on one side, then there are positive constants C and δ such that every graph with n vertices and C n3/2 – δ edges contains a copy of H. This answers a question by Erdős from 1988. The proof relies on a novel variant of the dependent random choice technique which may be of independent interest. This is joint work with David Conlon.
    Tags:
  • Jineon Baek, On the off-diagonal Erdős-Szekeres convex polygon problem

    On the off-diagonal Erdős-Szekeres convex polygon problem
    Jineon Baek (백진언)
    NIMS, Daejeon
    2018/09/10 Mon 5PM-6PM (Room 1401 of Bldg. E6-1)
    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.
    Tags:
  • Hong Liu, Enumerating sets of integers with multiplicative constraints

    Enumerating sets of integers with multiplicative constraints
    Hong Liu
    Mathematics Institute, University of Warwick, Warwick, UK
    2018/9/3 Mon 5PM
    Counting problems on sets of integers with additive constraints have been extensively studied. In contrast, the counting problems for sets with multiplicative constraints remain largely unexplored. In this talk, we will discuss two such recent results, one on primitive sets and the other on multiplicative Sidon sets. Based on joint work with Peter Pach, and with Peter Pach and Richard Palincza.
    Tags:

Monthly Archives