Final doctoral examination and defense of dissertation of Youngho Yoo, June 10, 2022

Final doctoral examination and defense of dissertation of Youngho Yoo, June 10, 2022

Title: Erdos-Posa theorems for undirected group-labelled graphs

Thesis draft: https://people.math.gatech.edu/~yyoo41/thesis.pdf

Date: June 10, 2022
Time: 11:00am EST
Location: Skiles 006
Zoom link: https://gatech.zoom.us/j/96860495360?pwd=cktMRVVqMDRtVnJsb3ZLRll1bFRJQT09

Meeting ID: 968 6049 5360
Passcode: 823463

Advisor: Dr. Xingxing Yu, School of Mathematics, Georgia Institute of Technology

Committee:
Dr. Anton Bernshteyn, School of Mathematics, Georgia Institute of Technology
Dr. Grigoriy Blekherman, School of Mathematics, Georgia Institute of Technology
Dr. Chun-Hung Liu, Department of Mathematics, Texas A&M University
Dr. Mohit Singh, School of Industrial and Systems Engineering, Georgia Institute of Technology

Reader: Dr. Chun-Hung Liu, Department of Mathematics, Texas A&M University

Abstract:

Erdos and Posa proved in 1965 that cycles satisfy an approximate packing-covering duality. Finding analogous approximate dualities for other families of graphs has since become a highly active area of research due in part to its algorithmic applications. In this thesis we investigate the Erdos-Posa property of various families of constrained cycles and paths by developing new structural tools for undirected group-labelled graphs.

Our first result is a refinement of the flat wall theorem of Robertson and Seymour to undirected group-labelled graphs. This structure theorem is then used to prove the Erdos-Posa property of A-paths of length 0 modulo p for a fixed odd prime p, answering a question of Bruhn and Ulmer. Further, we obtain a characterization of the abelian groups G and elements g for which A-paths of weight g satisfy the Erdos-Posa property. These results are from joint work with Robin Thomas.

We extend our structural tools to graphs labelled by multiple abelian groups and consider the Erdos-Posa property of cycles whose weights avoid a fixed finite subset in each group. We find three types of topological obstructions and show that they are the only obstructions to the Erdos-Posa property of such cycles. This is a far-reaching generalization of a theorem of Reed that Escher walls are the only obstructions to the Erdos-Posa property of odd cycles. Consequently, we obtain a characterization of the sets of allowable weights in this setting for which the Erdos-Posa property holds for such cycles, unifying a large number of results in this area into a general framework. As a special case, we characterize the integer pairs (L,M) for which cycles of length L mod M satisfy the Erdos-Posa property. This resolves a question of Dejter and Neumann-Lara from 1987. Further, our description of the obstructions allows us to obtain an analogous characterization of the Erdos-Posa property of cycles in graphs embeddable on a fixed compact orientable surface. This is joint work with Pascal Gollin, Kevin Hendrey, O-joung Kwon, and Sang-il Oum.