O-joung Kwon (권오정), On low rank-width colorings

May 14th, 2017
On low rank-width colorings
O-joung Kwon (권오정)
Technische Universitat Berlin, Berin, Germany
2017/6/09 Friday 11AM
We introduce the concept of low rank-width colorings, generalizing the notion of low tree-depth colorings introduced by Nešetřil and Ossona de Mendez in [Grad and classes with bounded expansion I. Decompositions. EJC 2008]. We say that a class 𝓒 of graphs admits low rank-width colorings if there exist functions N:ℕ→ℕ and Q:ℕ→ℕ such that for all p∈ℕ, every graph G∈𝓒 can be vertex colored with at most N(p) colors such that the union of any i≤p color classes induces a subgraph of rank-width at most Q(i).
Graph classes admitting low rank-width colorings strictly generalize graph classes admitting low tree-depth colorings and graph classes of bounded rank-width. We prove that for every graph class 𝓒 of bounded expansion and every positive integer r, the class {Gr: G∈𝓒} of r-th powers of graphs from 𝓒, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. All of these classes have unbounded rank-width and do not admit low tree-depth colorings. We also show that the classes of interval graphs and permutation graphs do not admit low rank-width colorings. In this talk, we provide the color refinement technique necessary to show the first result. This is joint work with Sebastian Sierbertz and Michał Pilipczuk.

Andreas Holmsen, Nerves, minors, and piercing numbers

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.

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

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.

Dieter Spreen, Bi-Topological Spaces and the Continuity Problem

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.

Otfried Cheong, Putting your coin collection on a shelf

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.