Tangle-tree duality in abstract separation systems
From MaRDI portal
Publication:2217534
Abstract: We prove a general width duality theorem for combinatorial structures with well-defined notions of cohesion and separation. These might be graphs and matroids, but can be much more general or quite different. The theorem asserts a duality between the existence of high cohesiveness somewhere local and a global overall tree structure. We describe cohesive substructures in a unified way in the format of tangles: as orientations of low-order separations satisfying certain consistency axioms. These axioms can be expressed without reference to the underlying structure, such as a graph or matroid, but just in terms of the poset of the separations themselves. This makes it possible to identify tangles, and apply our tangle-tree duality theorem, in very diverse settings. Our result implies all the classical duality theorems for width parameters in graph minor theory, such as path-width, tree-width, branch-width or rank-width. It yields new, tangle-type, duality theorems for tree-width and path-width. It implies the existence of width parameters dual to cohesive substructures such as -blocks, edge-tangles, or given subsets of tangles, for which no width duality theorems were previously known. Abstract separation systems can be found also in structures quite unlike graphs and matroids. For example, our theorem can be applied to image analysis by capturing the regions of an image as tangles of separations defined as natural partitions of its set of pixels. It can be applied in big data contexts by capturing clusters as tangles. It can be applied in the social sciences, e.g. by capturing as tangles the few typical mindsets of individuals found by a survey. It could also be applied in pure mathematics, e.g. to separations of compact manifolds.
Recommendations
Cites work
- \(k\)-blocks: a connectivity invariant for graphs
- A short proof that every finite graph has a tree-decomposition displaying its tangles
- A unified treatment of linked and lean tree-decompositions
- Abstract separation systems
- All graphs have tree-decompositions displaying their topological ends
- Canonical trees of tree-decompositions
- Connectivity and tree structure in finite graphs
- Directed path-decompositions
- Duality theorems for blocks and tangles in graphs
- Ends and tangles
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XVI: Excluding a non-planar graph
- Graph theory
- scientific article; zbMATH DE number 1057879 (Why is no real title available?)
- Obstructions to branch-decomposition of matroids
- Partitions versus sets: a case of duality
- Profiles of separations: in graphs, matroids, and beyond
- Profinite separation systems
- Refining a tree-decomposition which distinguishes tangles
- Separations of sets
- Structural submodularity and tangles in abstract separation systems
- Submodular partition functions
- Tangle-tree duality: in graphs, matroids and beyond
- Tangles are Decided by Weighted Vertex Sets
- Tree sets
- Über n-fach zusammenhängende Eckenmengen in Graphen
Cited in
(22)- Packing and covering immersions in 4-edge-connected graphs
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- On objects dual to tree-cut decompositions
- Profinite separation systems
- Trees of tangles in abstract separation systems
- Structural submodularity and tangles in abstract separation systems
- Tangle-tree duality: in graphs, matroids and beyond
- Abstract separation systems
- Tree sets
- Representations of infinite tree sets
- A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
- Obtaining trees of tangles from tangle-tree duality
- Unifying duality theorems for width parameters in graphs and matroids (extended abstract)
- Trees of tangles in infinite separation systems
- Duality theorems for blocks and tangles in graphs
- Refining a tree-decomposition which distinguishes tangles
- Refining trees of tangles in abstract separation systems: inessential parts
- Point sets and functions inducing tangles of set separations
- Characterising 4-tangles through a connectivity property
- Untangling Gaussian mixtures
- Optimal trees of tangles: refining the essential parts
- A structural approach to tree decompositions of knots and spatial graphs
This page was built for publication: Tangle-tree duality in abstract separation systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2217534)
