Tangle structure trees II: trees of tangles and tangle-tree duality
Hanno von Bergen and Reinhard Diestel · 2026
Read Tangle structure trees II: trees of tangles and tangle-tree duality by Hanno von Bergen and Reinhard Diestel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-17756.txt.
Introduction
von Bergen and Diestel extend tangle structure trees, a data structure that lists all tangles of a graph or dataset. The trees also certify that no other tangles exist, locally or overall. With them, the authors derive fresh forms of the tree-of-tangles theorem. Their version covers F-tangles that need not be profiles. For star-based separation families, the trees convert into classic tree decompositions. That conversion restores the known tangle-tree duality picture.
Catalog record
| CREATOR | Hanno von Bergen and Reinhard Diestel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 205049 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.17756
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tangle structure trees II: trees of tangles and tangle-tree duality Hanno von Bergen and Reinhard Diestel Abstract . Tangle structure trees, introduced in [ 2 ] , offer a unified data structure that displays all the tangles of a graph or data set together with certificates for the non-existence of any other tangles, either locally or overall. In this paper we apply tangle structure trees to derive new versions of the two fundamental tangle theorems: the tree-of-tangles theorem, and the tangle-tree duality theorem. We extend the tree-of-tangles theorem to ℱ \mathcal{F} -tangles that need not be profiles. When ℱ \mathcal{F} consists of stars of separations, as it does in classical tangle-tree duality theorems, we show how to convert tangle structure trees that certify the non-existence of ℱ \mathcal{F} -tangles into tree-decompositions that certify this in the way known from graph tangles, as S S -trees over ℱ \mathcal{F} . 1. Introduction In this sequel to [ 2 ] we explore further applications of tangle structure trees . These are data structures, introduced in [ 2 ] , which simultaneously display • all the tangles of a given graph or abstract separation system; and • for all its orientations that are not tangles, certificates of why they are not. Previously, there were two separate types of theorem in tangle theory for these two purposes: tree-of-tangle theorems, which display all the tangles of a graph or data set in a tree-like way that ‘distinguishes’ different tangles by specifying a minimum-order separation that they orient differently; and tangle-tree duality theorems that display, also in a tree-like way, certificates for why the various orientations of the separation system are not tangles – typically in the form of small subsets of oriented separations that are forbidden in the given type of tangle. These two fundamental theorems, which exist in various forms and degrees of generality, are thought of as the two pillars of both graph and abstract tangle theory. The unified way in which tangle structure trees serve both these purposes still allows us to extract, if desired, separate corollaries of the two types. In [ 2 ] we did this for the second type: we derived new tangle-tree duality-type theorems for tangles whose defining forbidden subsets were not ‘stars’ of separations, nested sets of typically three oriented separations pointing towards each other. All previously known tangle-tree duality theorems, in particular those for graphs, were for tangles defined by excluding such stars. Our first main result in this paper is to extract from the tangle structure trees established in [ 2 ] a new theorem of the first type: a tree-of-tangles theorem for tangles whose set \mathcal{F} of defining forbidden subsets need not form a ‘profile’. All known tree-of-tangles theorems so far are for profiles, in fact, for robust profiles. These are still a sweeping generalization of graph tangles. But we shall prove here that we can generalize them further: we shall obtain a tree-of-tangles theorem for all \mathcal{F} -tangles whose set \mathcal{F} of forbidden subsets of oriented separations is robust, even if not a profile. Our second main result is about \mathcal{F} -tangles whose set \mathcal{F} of forbidden subsets consists of stars of separations, as in all the classical tangle-tree duality theorems. We prove a general conversion theorem, which allows us to extract from our tangle structure tree for \mathcal{F} -tangles, of a separation system {\hskip-1.0pt{{{\mathop{\kern 0.0ptS}\limits^{\kern 3.0pt\raise 0.45206pt\vbox to0.0pt{\hbox{$\scriptscriptstyle\rightarrow$}\vss}}}}}\hskip-1.0pt} , say, an S -tree over \mathcal{F} if S admits no \mathcal{F} -tangles. Such an ‘ S -tree over \mathcal{F} ’ is the tree structure in the most general tangle-tree duality theorems known so far for abstract separation systems (which include graphs), proved in [ 7 ] . Our conversion theorem allows us to re-prove the main result of [ 7 ] from the premise for the existence of tangle structure trees, which differs from the premise of the tangle-tree duality theorem in [ 7 ] . However we demonstrate that from our premise for the existence of tangle structure trees we can derive a weaker version of the premise in [ 7 ] , the version used in practice when the duality theorem from [ 7 ] is applied in [ 6 ] . As a consequence, we shall be able in [ 3 ] to use our conversion theorem, coupled with the existence theorems for tangle structure trees in [ 2 ] , to derive all the known applications of the tangle-tree duality theorem in [ 7 ] to concrete structures, such as graphs, matroids, or data sets [ 6 ] . The paper is organized as follows. In Section 2 we give a summary of tangle basics, just what is technically needed to read this paper. More on graph tangles can be found in [ 11 ] , more on abstract tangles and their applications in [ 8 , 9 , 10 ] . In Section 3 we introduce tangle structure trees and summarize the main results from [ 2 ] ; more on this, including motivational background, can be found there. Section 4 contains our conversion theorem that extracts from a tangle structure tree, of a separation system {\hskip-1.0pt{{{\mathop{\kern 0.0ptS}\limits^{\kern 3.0pt\raise 0.45206pt\vbox to0.0pt{\hbox{$\scriptscriptstyle\rightarrow$}\vss}}}}}\hskip-1.0pt} that has no \mathcal{F} -tangles, an S -tree over \mathcal{F} . Section 5 is an interlude on submodular order functions for separations, which is needed in the rest of the paper; we show how a non-injective submodular order function can be extended to an injective one without losing submodularity. The tree-of-tangles theorem for \mathcal{F} -tangles with arbitrary robust exclusion sets \mathcal{F} is proved in Section 6 . In Section 7 we show how to recover the essence of the tangle-tree duality theorem of [ 7 ] from our conversion theorem and our existence theorem for tangle structure trees. 2. Separation systems and their tangles In this section we introduce the terminology that abstract tangle theory requires, following [ 8 ] . 1 1 1 There is one difference to [ 8 ] : for historical reasons, the partial ordering on {\hskip-1.0pt{{{\mathop{\kern 0.0ptS}\limits^{\kern 3.0pt\raise 0.45206pt\vbox to0.0pt{\hbox{$\scriptscriptstyle\rightarrow$}\vss}}}}}\hskip-1.0pt} used there is the inverse of ours. So terms like ‘large’ and ‘small’, infima and suprema etc, are reversed. Readers familiar with [ 2 ] may skip this section. Tangles of graphs are ways of orienting their separations, each towards one of its two sides. Abstract tangles are designed to work in scenarios where there need not be anything to ‘separate’. In order to retain our intuition from graphs, however, we continue to refer to the things of which our abstract tangles pick one of two variants (which they will indeed do) as ‘separations’. These are defined by noting some key properties of graph separations and making them into axioms, as follows. A separation system ({\hskip-1.0pt{{{\mathop{\kern 0.0ptS}\limits^{\kern 3.0pt\raise 0.45206pt\vbox to0.0pt{\hbox{$\scriptscriptstyle\rightarrow$}\vss}}}}}\hskip-1.0pt},\leqslant,^{*}) is a set {\hskip-1.0pt{{{\mathop{\kern 0.0ptS}\limits^{\kern 3.0pt\raise 0.45206pt\vbox to0.0pt{\hbox{$\scriptscriptstyle\rightarrow$}\vss}}}}}\hskip-1.0pt} , whose elements we call oriented separations , that comes with a partial ordering \leqslant on {\hskip-1.0pt{{{\mathop{\kern 0.0ptS}\limits^{\kern 3.0pt\raise 0.45206pt\vbox to0.0pt{\hbox{$\scriptscriptstyle\rightarrow$}\vss}}}}}\hskip-1.0pt} and an order-reversing involution {}^{*}\colon{\hskip-1.0pt{{{\mathop{\kern 0.0ptS}\limits^{\kern 3.0pt\raise 0.45206pt\vbox to0.0pt{\hbox{$\scriptscriptstyle\rightarrow$}\vss}}}}}\hskip-1.0pt}\to{\hskip-1.0pt{{{\mathop{\kern 0.0ptS}\limits^{\kern 3.0pt\raise 0.45206pt\vbox to0.0pt{\hbox{$\scriptscriptstyle\rightarrow$}\vss}}}}}\hskip-1.0pt} . Thus, for any two elements 2 2 2 We often denote the elements of {\hskip-1.0pt{{{\mathop{\kern 0.0ptS}\limits^{\kern 3.0pt\raise 0.45206pt\vbox to0.0pt{\hbox{$\scriptscriptstyle\rightarrow$}\vss}}}}}\hskip-1.0pt} by letters with an arrow, in either direction, precisely in