Tangle-Tree Duality: In Graphs, Matroids and Beyond
Tangle-Tree Duality: In Graphs, Matroids and Beyond
复制标题
缠结树对偶性：在图、拟阵及其他领域
作者：
R. Diestel;Sang
应用抽象分离系统中的一个新的缠结树对偶定理，得到了图和拟阵中宽度参数的缠结树型对偶定理，并进一步得到了大数据集上簇存在的对偶定理.我们的应用图包括新的，纠缠型，对偶定理树的宽度，路径宽度，和树分解的小粘附。相反，我们表明，雕刻宽度是对偶的边缘缠结。对于拟阵，我们得到了一个关于树宽的缠结型对偶定理。我们的结果也可用于图子式理论中所有经典的宽度参数对偶定理的简短证明，如路宽，树宽，分支宽度和秩宽度。
We apply a recent tangle-tree duality theorem in abstract separation systems to derive tangle-tree-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 tangle-type duality theorem for tree-width. Our results can also 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.