Algebra and Combinatorics Seminar

Date: February 14, 2020

Time: 3:00PM - 3:50PM

Location: BLOC 628

Speaker: Chun-Hung Liu, Texas A&M University

Title: Well-quasi-ordering graphs by the topological minor relation

Abstract: A well-quasi-ordering is a reflexive and transitive binary relation such that every infinite sequence has a non-trivial increasing subsequence. The study of well-quasi-ordering can be dated back to two conjectures of Vazsonyi proposed in 1940s stating that trees and subcubic graphs are well-quasi-ordered by the topological minor relation. Both conjectures have been solved, where the second conjecture is particularly difficult in the sense that the only known proof is via Robertson and Seymour's celebrated Graph Minor Theorem stating that the minor relation is a well-quasi-ordering. On the other hand, the topological minor relation is not a well-quasi-ordering in general. Robertson in 1980s conjectured that the known obstruction is the only obstruction. Joint with Robin Thomas, we solved Robertson's conjecture and proved a characterization of well-quasi-ordered topological-minor ideals. We will sketch some ideas in the proof.