Monday, June 14, 3pm ET (8pm BST, 7am Tue NZST)
Youngho Yoo, Georgia Tech
Packing A-paths of length 0 modulo a prime
Abstract:
An $A$-path is a nontrivial path with its endpoints in a vertex set $A$ that is internally disjoint from $A$. In 1961, Gallai showed that $A$-paths satisfy an approximate packing-covering duality, also known as the Erdős-Pósa property. There are many generalizations and variants of this result. In this talk, we show that the Erdős-Pósa property holds for $A$-paths of length 0 mod $p$ for every prime $p$, answering a question of Bruhn and Ulmer. The proof uses structure theorems for undirected group-labelled graphs. We also give a characterization of abelian groups $\Gamma$ and elements $\ell \in \Gamma$ for which the Erdős-Pósa property holds for $A$-paths of weight $\ell$ in undirected $\Gamma$-labelled graphs. Joint work with Robin Thomas.