Tournament pathwidth and topological containment

-
Alexandra Fradkin, Princeton University
Fine Hall 224

In this talk we will prove that for a set $S$ of tournaments the following three statements are equivalent: - there exists $k$ such that all members of $S$ have pathwidth less than $k$; - there exists $k$ such that no member of $S$ contains $k$ vertices that are pairwise $k$-connected; - there exists a digraph $H$ such that no member of $S$ contains a subdivision of $H$. As a consequence, we obtain a polynomial time algorithm to test whether a tournament contains a subdivision of a fixed digraph $H$. We note that the equivalent problem in general digraphs is NP-complete. Joint work with Paul Seymour.