Graph structures and well-quasi-ordering
Dr.劉俊宏Department of Mathematics, Princeton University 上午 9:30–11:00 鴻經館 107 室Abstract:
Robertson and Seymour proved that graphs are well-quasi-ordered by the minor relation and the weak immersion relation. In other words, given
infinitely many graphs, one graph contains another as a minor (or a weak immersion, respectively). Unlike the relation of minor and weak immersion, the topological minor relation does not well-quasi-order graphs in general. However, Robertson conjectured in the late 1980’s that for every positive integer k, the topological minor relation well-quasi-orders graphs that do not contain a topological minor isomorphic to the path of length k with each edge duplicated. This conjecture was proved by Thomas and I. We will sketch the idea of the proof in this talk. In addition, we will give a structure theorem for excluding a fixed graph as a topological minor. Such structure theorems were previously obtained by Grohe and Marx and by Dvorak, but we push one of the bounds in their theorems to the optimal value. This improvement is needed for our proof of Robertson’s conjecture.