Deciders for tangles of set separations
Reinhard Diestel, Christian Elbracht, Raphael W. Jacobs · arXiv (Cornell University) · 2021
Tangles, as introduced by Robertson and Seymour, were designed as an indirect way of capturing clusters in graphs and matroids. They have since been shown to capture clusters in much broader discrete structures too. But not all tangles are induced by a cluster. We characterise those that are. We offer two such characterisations. The first is in terms of how many small sides of a tangle's separations it takes to cover the graph or matroid. The second uses a new notion of duality for separation systems that do not necessarily come from graphs or matroids.