Algebra and Combinatorics Seminar

Date: March 5, 2021

Time: 3:00PM - 4:00PM

Location: Zoom

Speaker: Chun-Hung Liu, TAMU

Title: Well-quasi-ordering digraphs by the strong immersion 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 was stimulated by two conjectures of Vazsonyi in 1940s: trees and subcubic graphs are well-quasi-ordered by the topological minor relation. It is known that the topological minor relation does not well-quasi-order all graphs. Nash-Williams in 1960s introduced the notion of strong immersion and conjectured that the strong immersion relation well-quasi-orders all graphs, which is a common generalization of both conjectures of Vazsonyi. In this talk we consider strong immersion on digraphs. Paths that change direction arbitrarily many times form an infinite antichain with respect to the strong immersion relation. In this talk, we will prove that it is the only obstruction. Namely, for any integer k, digraphs with no paths that change direction at least k times are well-quasi-ordered by the strong immersion relation. Joint work with Irene Muzi.