{"id":{"repo_id":"gatech","oai_identifier":"oai:repository.gatech.edu:1853/67225"},"canonical_url":"https://search.dev.ndltd.org/etd/gatech/oai:repository.gatech.edu:1853/67225","repository":{"repo_id":"gatech","name":"Georgia Tech","base_url":"https://repository.gatech.edu/server/oai/request"},"display":{"title":"Erdos-Posa theorems for undirected group-labelled graphs","abstract":"Erdős and Pósa 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 Erdős-Pósa 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 Erdős-Pósa 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 Γ and elements l ∈ Γ for which A-paths of weight l satisfy the Erdős-Pósa 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 Erdős-Pósa 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 Erdős-Pósa property of such cycles. This is a far-reaching generalization of a theorem of Reed that Escher walls are the only obstructions to the Erdős-Pósa property of odd cycles. Consequently, we obtain a characterization of the sets of allowable weights in this setting for which the Erdős-Pósa 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, z) for which cycles of length l mod z satisfy the Erdős-Pósa 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 Erdős-Pósa 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.","abstract_html":"Erdős and Pósa 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 Erdős-Pósa 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 Erdős-Pósa 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 Γ and elements l ∈ Γ for which A-paths of weight l satisfy the Erdős-Pósa 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 Erdős-Pósa 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 Erdős-Pósa property of such cycles. This is a far-reaching generalization of a theorem of Reed that Escher walls are the only obstructions to the Erdős-Pósa property of odd cycles. Consequently, we obtain a characterization of the sets of allowable weights in this setting for which the Erdős-Pósa 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, z) for which cycles of length l mod z satisfy the Erdős-Pósa 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 Erdős-Pósa 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.","abstract_has_math":false,"creators":["Yoo, Youngho"],"institution":"Georgia Institute of Technology","degree_name":null,"degree_level":"Doctoral","degree_discipline":null,"degree_department":"Mathematics","school":null,"contributors":[],"advisors":["Yu, Xingxing"],"committee_chairs":[],"committee_members":["Bernshteyn, Anton","Blekherman, Grigoriy","Liu, Chun-Hung","Singh, Mohit"],"year":2022,"date_issued":"2022-06-14","date_published":"2022-06-14","updated_at":"2026-07-27T19:49:22Z","subjects":["Graph theory, combinatorics"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1853/67225","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Yu, Xingxing"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Bernshteyn, Anton","Blekherman, Grigoriy","Liu, Chun-Hung","Singh, Mohit"]},{"key":"dc:contributor.department","label":"Department","values":["Mathematics"]},{"key":"dc:creator","label":"Author","values":["Yoo, Youngho"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-08-25T13:34:03Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-08-25T13:34:03Z"]},{"key":"dc:date.issued","label":"Date","values":["2022-06-14"]},{"key":"dc:publisher","label":"Institution","values":["Georgia Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Text"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph theory, combinatorics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1853/67225"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Erdős and Pósa 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 Erdős-Pósa 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 Erdős-Pósa 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 Γ and elements l ∈ Γ for which A-paths of weight l satisfy the Erdős-Pósa 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 Erdős-Pósa 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 Erdős-Pósa property of such cycles. This is a far-reaching generalization of a theorem of Reed that Escher walls are the only obstructions to the Erdős-Pósa property of odd cycles. Consequently, we obtain a characterization of the sets of allowable weights in this setting for which the Erdős-Pósa 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, z) for which cycles of length l mod z satisfy the Erdős-Pósa 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 Erdős-Pósa 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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Erdos-Posa theorems for undirected group-labelled graphs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Yu, Xingxing"],"dc:contributor.committeemember":["Bernshteyn, Anton","Blekherman, Grigoriy","Liu, Chun-Hung","Singh, Mohit"],"dc:contributor.department":["Mathematics"],"dc:creator":["Yoo, Youngho"],"dc:date.accessioned":["2022-08-25T13:34:03Z"],"dc:date.available":["2022-08-25T13:34:03Z"],"dc:date.issued":["2022-06-14"],"dc:description.abstract":["Erdős and Pósa 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 Erdős-Pósa 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 Erdős-Pósa 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 Γ and elements l ∈ Γ for which A-paths of weight l satisfy the Erdős-Pósa 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 Erdős-Pósa 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 Erdős-Pósa property of such cycles. This is a far-reaching generalization of a theorem of Reed that Escher walls are the only obstructions to the Erdős-Pósa property of odd cycles. Consequently, we obtain a characterization of the sets of allowable weights in this setting for which the Erdős-Pósa 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, z) for which cycles of length l mod z satisfy the Erdős-Pósa 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 Erdős-Pósa 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."],"dc:description.degree":["Ph.D."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1853/67225"],"dc:language.iso":["en_US"],"dc:publisher":["Georgia Institute of Technology"],"dc:subject":["Graph theory, combinatorics"],"dc:title":["Erdos-Posa theorems for undirected group-labelled graphs"],"dc:type":["Text"],"thesis:degree_level":["Doctoral"]},"updated_at":"2026-07-27T19:49:22Z"}