Algebra and Combinatorics Seminar

Date: March 12, 2021

Time: 3:00PM - 4:00PM

Location: Zoom

Speaker: Youngho Yoo, Georgia Tech

Title: Packing A-paths and cycles with modularity constraints

Abstract: A classical result of Erdős and Pósa states that a graph without many disjoint cycles contains a small vertex set intersecting every cycle. The analogous statement fails however for odd cycles, as can be shown by large projective planar grids. In 1987, Dejter and Neumann-Lara raised the question of when this approximate packing-covering duality holds for cycles of length L mod M, and there had been minimal progress on this problem until recently. There are similar questions on packing A-paths (paths meeting a vertex set A at exactly its endpoints) with modularity constraints. Casting these problems in the more general setting of group-labelled graphs and studying their structure, we obtain a complete characterization of the integer pairs L and M for which the above approximate duality holds for A-paths and cycles of length L mod M. Joint work with Robin Thomas and with Pascal Gollin, Kevin Hendrey, O-joung Kwon, and Sang-il Oum.