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.

Date: Dec 16, 2020 at 15:00:00 h
Venue: Modalidad Vía Online.
Speaker: Chun-Hung Liu
Affiliation: Texas A&M University
Coordinator: José Verschae
More info at:
Event website
Abstract:
PDF

Posted on Dec 14, 2020 in ACGO, Seminars