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

Series
Graph Theory Working Seminar
Time
Tuesday, September 22, 2020 - 3:45pm for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Youngho Yoo – Georgia Institute of Technology – yyoo41@math.gatech.eduhttp://people.math.gatech.edu/~yyoo41/
Organizer

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.