Tournament pathwidth and topological containment
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 NPcomplete. Joint work with Paul Seymour.