Matroid Theory Seminar - Tony Huynh

Thursday, March 3, 2016 4:00 pm - 4:00 pm EST (GMT -05:00)

Title: A unified Erd\H os-P\'osa theorem for constrained cycles

Speaker: Tony Huynh
Affiliation: Universite Libre de Bruxelles
Room: MC 5417

Abstract: In 1962, Erd\H os and P\'osa proved that for every positive integer $k$, there exists a constant $f(k)$ such that every graph $G$ either contains $k$ vertex-disjoint cycles or a set $X$ of at most $f(k)$ vertices such that $G-X$ contains no cycle.  This theorem has since been generalized to cycles satisfying further constraints.  For example, odd cycles, $S$-cycles, long cycles, odd $S$-cycles, and long $S$-cycles.  We prove a theorem that contains all of these results as well as some new ones.  

It turns out that the right objects to study are doubly group-labeled graphs.  A doubly group-labeled graph is an oriented graph with edge labels from the direct sum of two abelian groups.  A cycle is doubly non-zero, if it is non-zero in both coordinates.  We recover all the aforementioned results via an Erd\H os-P\'osa theorem for doubly non-zero cycles. We prove this via a refinement of the Flat Wall Theorem of Robertson and Seymour to doubly group-labeled graphs, which may be of independent interest.  

This is joint work with Felix Joos and Paul Wollan.