Archive for the ‘2017’ Category

« Older Entries
Newer Entries »

Andreas Holmsen, Nerves, minors, and piercing numbers

Friday, April 28th, 2017
Nerves, minors, and piercing numbers
Andreas Holmsen
Department of Mathematical Sciences, KAIST
2017/5/08 Mon 4PM-5PM
We will give a topological generalization of the planar (p,q) theorem due to Alon and Kleitman. In particular we will show that the assertion of the (p,q) theorem holds for families of open connected sets in the plane under the hypothesis that the intersection of any subfamily is empty or connected. The proof is based on a surprising connection between nerve complexes and complete minors in graphs. This is join work with Minki Kim and Seunghun Lee.

Tags:
Posted in 2017, KAIST Discrete Math Seminar | Comments Closed

Brendan Rooney, Eigenpolytopes, Equitable Partitions, and EKR-type Theorems

Sunday, April 16th, 2017
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:
Posted in 2017, KAIST Discrete Math Seminar | Comments Closed

Dieter Spreen, Bi-Topological Spaces and the Continuity Problem

Sunday, April 9th, 2017
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:
Posted in 2017, KAIST Discrete Math Seminar | Comments Closed

Otfried Cheong, Putting your coin collection on a shelf

Saturday, March 18th, 2017
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:
Posted in 2017, KAIST Discrete Math Seminar | Comments Closed

[SoC Colloquium] Helmut Alt, Packing Problems: Algorithms and Complexity

Tuesday, March 7th, 2017
Packing Problems: Algorithms and Complexity
Helmut Alt
Department of Computer Science, Freie Universität Berlin
2017/3/13 Mon 4PM-6PM
Packing problems are concerned with positioning geometric objects so that they do not overlap and require an amount of space as small as possible. They have been investigated within mathematics for centuries starting with the famous Kepler conjecture. There are many surprising properties and open problems in connection with packing. The lecture will give a short survey about these “classical” issues but then concentrate on algorithms for packing. Since already the most simple variants are NP-hard, it makes sense to look for efficient approximation algorithms. We will present constant factor approximations for packing rectangles and convex polygons into containers which are minimum area rectangles or convex sets. Algorithms for analogous problems concerning three-dimensional objects will be presented, as well.
This is joint research with Mark de Berg, Christian Knauer, Léonard von Niederhäusern, and Nadja Scharf.

Tags:
Posted in 2017, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »