Matroid Theory Seminar - Benson Joeris

Title: Tangles and tree-decompositions

Abstract: A $k$-tangle is an abstract structure representing a '$k$-connected component' of a graph or matroid -- e.g., each biconnected component of a graph corresponds to a distinct 2-tangle. A $k$-tree-decomposition constructs a graph or matroid by combining smaller pieces in such a way that the connectivity between pieces is limited -- e.g., a clique-sum construction of a graph, using clique-sums with at most $k$ vertices. Robertson and Seymour showed that a graph or matroid has no $k$-tangle if and only if it can be constructed from pieces of bounded size using a $(k-1)$-tree-decomposition. I will discuss this duality and other related properties of tangles and tree-decompositions.