Tangle-tree duality: in graphs, matroids and beyond

Abstract

We apply a recent duality theorem for tangles in abstract separation systems to derive tangle-type duality theorems for width-parameters in graphs and matroids. We further derive a duality theorem for the existence of clusters in large data sets. Our applications to graphs include new, tangle-type, duality theorems for tree-width, path-width, and tree-decompositions of small adhesion. Conversely, we show that carving width is dual to edge-tangles. For matroids we obtain a duality theorem for tree-width. Our results can be used to derive short proofs of all the classical duality theorems for width parameters in graph minor theory, such as path-width, tree-width, branch-width and rank-width.

arXiv admin note: text overlap with arXiv:1406.3797

References in corpus (2)

• Abstract Separation Systems
• Partitions versus sets : a case of duality

Cited by in corpus (6)

• Tangle-tree duality in abstract separation systems
• Trees of tangles in abstract separation systems
• Packing and Covering Immersions in 4-Edge-Connected Graphs
• Trees of tangles in infinite separation systems
• Obtaining trees of tangles from tangle-tree duality
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three