Tangle-tree duality: in graphs, matroids and beyond (Q2338616)

The authors build upon a general width duality theorem in abstract separation systems with well-defined notions of cohesion and separation, which establishes duality between the existence of high cohesiveness at a local level and a global tree structure, and which they have proved recently by the authors [``Tangle-tree duality in abstract separation systems'', Preprint, \url{arXiv:1701.02509}]. In the present paper this theorem is applied to derive tangle-tree-type duality theorems for tree-width, path-width, tree-decompositions of small adhesion in graphs, for tree-width in matroids, and its application to data science is showcased through derivation of the duality theorem for the existence of clusters in large data sets. Its power is further demonstrated by obtaining the classical duality theorems for width parameters in graph minor theory (such as path-width, tree-width, branch-width and rank-width) as its corollaries.