Packing A-paths and cycles in undirected group-labelled graphs

Graph Theory Working Seminar
Tuesday, September 22, 2020 - 3:45pm for 1 hour (actually 50 minutes)
Location For password, please email Anton Bernshteyn (bahtoh ~at~
Youngho Yoo – Georgia Institute of Technology – yyoo41@math.gatech.edu
Anton Bernshteyn

An $A$-path is a path whose intersection with a vertex set $A$ is exactly its endpoints. We show that, for all primes $p$, the family of $A$-paths of length $0 \,\mathrm{mod}\, p$ satisfies an approximate packing-covering duality known as the Erdős-Pósa property. This answers a recent question of Bruhn and Ulmer. We also show that, if $m$ is an odd prime power, then for all integers $L$, the family of cycles of length $L \,\mathrm{mod}\, m$ satisfies the Erdős-Pósa property. This partially answers a question of Dejter and Neumann-Lara from 1987 on characterizing all such integer pairs $L$ and $m$. Both results are consequences of a structure theorem which refines the Flat Wall Theorem of Robertson and Seymour to undirected group-labelled graphs analogously to a result of Huynh, Joos, and Wollan in the directed setting. Joint work with Robin Thomas.