Tangles, Trees of Tangles, and Submodularity

Abstract

This thesis treats tangles in abstract separation systems, a way of characterising dense or well-connected substructure or ‘clusters’ in various contexts, and the underlying submodularity properties that one can demand of these separation systems. Tangles describe clusters in an indirect way: not by specifying explicit parts of a data structure, but only by declaring for every way of cutting the structure into two parts which side the cluster lies. This approach allows to capture concepts of clusters where the membership of individual points in a specific cluster is uncertain. The concept of tangles originates from graph minor theory, where they are used to characterise how tree-like a graph is. This thesis is divided into three parts.

In Part I we present two instances of structure induced by a single tangle. An open question about tangles in graphs is whether each of them has a decider set: a set 𝑋 of vertices so that for every separation (𝐴, 𝐵) where the tangle points to 𝐵 more vertices of 𝑋 are in 𝐵 than in 𝐴. In Chapter 3 we show that a weighted version of deciders exists, i.e., that there always is a non-negative weight function defined on the vertices such that, for every separation (𝐴, 𝐵) in the tangle, the sum over the weights in 𝐵 is larger than the sum over the weights in 𝐴. Chapter 4 covers dual tangles in the setting of bipartite graphs. Given a bipartite graph with partition classes 𝑋 and 𝑌, we show how one can define tangles in the separations of 𝑋 and 𝑌, so that tangles in 𝑋 induce tangles in 𝑌 – and vice versa – in a natural way. These dual tangles turn out to also be witnessed by a new kind of tangles defined on the set separations of the edge set, which we cover in Section 4.2.

Part II, is devoted to trees of tangles. The tree-of-tangles theorem is one of the fundamental theorems of tangle theory. In fact, the term is used to describe a whole class of theorems, all of which state that for every (sufficiently nice) set of tangles 𝒯, then there exists a nested set of separations 𝑁 containing a distinguishing separation for every pair of tangles in 𝒯. Such a nested set reveals a tree-shaped arrangement of the tangles in the separation system. Depending on the conditions on the set of tangles 𝒯, these theorems guarantee additional properties of the set 𝑁: canonicity and/or the efficiency of the distinguishing separations. Chapter 5 introduces our splinter lemmas, a framework which allows us to prove in a unified and simple way the most relevant existing tree-of-tangles theorems. They also allow as introduce some of our own tree-of-tangles theorems; for example, for profiles in sequences of separation systems. We also extend this framework to an infinite setting in Sections 5.8 and 5.9, re-proving two existence theorems on tree-decompositions of infinite graphs by introducing a new theorem which sits midway between the two. We introduce another application, this time to edge-connectivity in infinite graphs, in Section 5.10. Chapter 6 comprises proofs of tree-of-tangles theorems as well. And while the theorems themselves are unspectacular, especially in light of Chapter 5, the extraordinary aspect is the method by which we prove those theorems: by applying the tangle–tree duality theorem. The tangle–tree duality theorem and the tree-of-tangles theorem are the two fundamental pillars on which tangle theory stands. But while both can give a tree-like arrangement of separations as a result, the way in which you apply them is very different: the tree-of-tangles theorem gives you tree if there are tangles, the tangle–tree duality theorem gives you a tree if there is no tangle. In Chapter 6 we push the limits of the tangle–tree duality theorem and make it produce a tree of tangles. Finally, Chapter 7 introduces a heuristic approach for computing tangles and trees of tangles. There we explain how, without perfect knowledge of a complete separation system, one can compute an approximation of the tangles and build trees of tangles for such approximate tangles.

The final part, Part III, is concerned with the structural properties of the separation systems – specifically with submodularity. Submodularity is a central property in tangle theory and features in virtually every proof concerned with tangles. However, there are multiple gradations of submodularity conditions. Chapter 8 explores the relationship between the three natural submodularity conditions that one can impose onto a separation system: submodularity, (structural) submodularity inside a universe of separations, and order-induced submodularity, where each is stronger requirement than the previous. In particular, in Section 8.2 we show how the submodularity of a separation system on its own can be witnessed by constructing an appropriate universe around it, linking the first and second condition. On the other hand, we show in Section 8.3 that order-induced submodularity is a strictly stronger property than mere submodularity in a universe, making the distinction between the second and third condition explicit. Beyond comparing the types of submodularity, we develop two decomposition theorems for separation systems which satisfy submodularity of the second type within a distributive universe of separations. Chapter 9 introduces one fundamental question about submodular separation systems: Given a submodular separation system, is there always a separation that we can delete, so that the remainder is still submodular? If we can find a sequence of separations that we can delete one after the other while maintaining submodularity until we reach the empty set, we speak of an unravelling. We show the existence of unravellings for the strongest and for the weakest concept of submodularity in Section 9.2 and Section 9.4, respectively. For the third concept, (structural) submodularity inside a universe of separations, we give a counterexample in Section 9.3.