Seminars in April 2017

  • Brendan Rooney, Eigenpolytopes, Equitable Partitions, and EKR-type Theorems
    Eigenpolytopes, Equitable Partitions, and EKR-type Theorems
    Brendan Rooney
    Department of Mathematical Sciences, KAIST
    2017/4/24 Monday 5PM
    The Erdos-Ko-Rado Theorem is a classic result about intersecting families of sets. More recently, analogous “EKR-type” type theorems have been developed for other types of objects. For example, non-trivially intersecting vector spaces, and overlapping strings. In this seminar we will give a proof of the EKR Theorem for permutations in Sn due to Godsil and Meagher. Along the way we will see some useful tools from algebraic graph theory. Namely, a bound on the maximum size of an independent set in a graph, equitable partitions, and eigenpolytopes.
    Tags:

  • Dieter Spreen, Bi-Topological Spaces and the Continuity Problem
    Bi-Topological Spaces and the Continuity Problem
    Dieter Spreen
    Department of Mathematics, Universität Siegen, Siegen, Germany
    2017/4/17 Mon 4PM-5PM
    The continuity problem is the question when effective (or Markov computable) maps between effectively given topological spaces are effectively continuous. It will be shown that this is always the case if the the range of the map is effectively bi-regular. As will be shown, such spaces appear quite naturally in the context of the problem.
    Tags:

  • Otfried Cheong, Putting your coin collection on a shelf
    Putting your coin collection on a shelf
    Otfried Cheong
    School of Computing, KAIST
    2017/04/03 Monday 4PM-5PM
    Imagine you want to present your collection of n coins on a shelf, taking as little space as possible – how should you arrange the coins?
    More precisely, we are given n circular disks of different radii, and we want to place them in the plane so that they touch the x-axis from above, such that no two disks overlap. The goal is to minimize the length of the range from the leftmost point on a disk to the rightmost point on a disk.
    On this seemingly innocent problem we will meet a wide range of algorithmic concepts: An efficient algorithm for a special case, an NP-hardness proof, an approximation algorithm with a guaranteed approximation factor, APX-hardness, and a quasi-polynomial time approximation scheme.
    Tags:

Monthly Archives