Algorithms, Combinatorics and Optimization Seminar Chun-Hung Liu
Princeton
Title: Erdös–Posa property

Abstract: A family F of graphs has the Erdös–Posa property if there exists a function f such that every graph either contains k disjoint subgraphs where each isomorphic to a member of F or contains a set of at most f(k) vertices intersecting all such subgraphs. The Erdös–Posa property describes the situation when the optimal solutions of the packing and covering problems can be bounded in terms of each others.

Erdös and Posa proved that the set of cycles has the Erdös–Posa property. This result was generalized by Robertson and Seymour in terms of graph minors. They proved that H is a graph such that the set of graphs containing H as a minor has the Erdös–Posa property if and only if H is planar. However, the Erdös–Posa property with respect to the topological minor containment is more subtle. I will present a complete characterization provided in joint work with Postle and Wollan for the graphs H in which the set of graphs containing H as a topological minor and answer a question of Robertson and Seymour. Our characterization is complicated, but a simple solution is unlikely to exist. I will also discuss how to avoid this complexity by considering other closely related containment relations.

Date: Thursday, April 20, 2017
Time: 3:30 pm
Location: Wean Hall 8220
Note: before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220