Mathematics Colloquium
Youngho Yoo
University of Alaska, Fairbanks
Title: Structure in group-labeled graphs and its applications
Date: Monday, March 31st
Place and Time: Love 101, 3:05-3:55 pm
Abstract. Can a cycle of length L modulo M be found in a given graph in polynomial time? This problem was first posed by Arkin, Papadimitriou, and Yannakakis (1991), motivated by periods of Markov chains, and reiterated in the study of graph databases and extremal graph theory. I will discuss recent work on the structure of group-labeled graphs that resolves this problem in a far more general form. Our work also provides a characterization of the topological obstructions to an approximate packing-covering duality for cycles of length L modulo M, resolving a problem of Dejter and Neumann-Lara (1988). I will further discuss applications of our work to other group-expressible length constraints.