Mathematical Sciences Department Colloquium
Youngho Yoo, Texas A&M
Tuesday, February 4th
12:00-1:00pm
Stratton 202
Title: Structure in group-labelled graphs and its applications
Abstract: Group-labelled graphs provide a unified framework that can encode many natural graph constraints. I will present recent work on the structure of unoriented group-labelled graphs that led to the resolution of two problems on modularity constraints, each of which had been open for over 30 years. The first, studied by Arkin, Papadimitriou, and Yannakakis in 1991, is on the existence of a polynomial time algorithm to detect cycles of length L modulo M; we settle this affirmatively for all L and M. The second, posed by Dejter and Neumann-Lara in 1987, is on an approximate packing-covering duality of cycles of length L modulo M; we settle this by characterizing the topological obstructions to this duality. Our results are proved in the general setting of group-labelled graphs and have further applications beyond modularity constraints.