KAIST Discrete Math Seminar

Let G be a graph on n vertices with independence number α. How large must a k-connected subgraph G contain? We shall present the best possible answers when α=2 and α=3. Some open questions will also be presented.
Joint work with Shinya Fujita (Yokohama City University, Japan) and Amites Sarkar (Western Washington University, USA).

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 {G^r: 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.

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.

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 S_n 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.

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.