Structural submodularity and tangles in abstract separation systems

DOI10.1016/J.JCTA.2019.05.001MaRDI QIDQ2318482zbMATH OpenOpenAlexWikidataFDO

Authors Reinhard Diestel, Joshua Erde, Daniel Weißauer

Publication date 15 August 2019

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.01439

zbMATH Keywords

cluster analysisgraph minorstanglesphylogenetic treestree-decompositionsabstract separation systems

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Abstract: We prove a tangle-tree theorem and a tangle duality theorem for abstract separation systems $vecS$ that are submodular in the structural sense that, for every pair of oriented separations, $vecS$ contains either their meet or their join defined in some universe $vecU$ of separations containing $vecS$. This holds, and is widely used, if $vecU$ comes with a submodular order function and $vecS$ consists of all its separations up to some fixed order. Our result is that for the proofs of these two theorems, which are central to abstract tangle theory, it suffices to assume the above structural consequence for $vecS$, and no order function is needed.

Recommendations

• Trees of tangles in abstract separation systems
• Obtaining trees of tangles from tangle-tree duality
• Abstract separation systems
• Tangle-tree duality in abstract separation systems
• Profinite separation systems

Cites work

• A unified treatment of linked and lean tree-decompositions
• Abstract separation systems
• Canonical tree-decompositions of a graph that display its \(k\)-blocks
• Canonical tree-decompositions of finite graphs. I: Existence and algorithms.
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Connectivity and tree structure in finite graphs
• Decomposition by clique separators
• Duality theorems for blocks and tangles in graphs
• Graph minors. X: Obstructions to tree-decomposition
• Obstructions to branch-decomposition of matroids
• On rigid circuit graphs
• Profiles of separations: in graphs, matroids, and beyond
• Refining a tree-decomposition which distinguishes tangles
• Tangle-tree duality: in graphs, matroids and beyond
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Tree sets
• Trees of tangles in abstract separation systems

Cited in

(9)

• A canonical tree-of-tangles theorem for structurally submodular separation systems
• Refining trees of tangles in abstract separation systems: inessential parts
• Tangle-tree duality in abstract separation systems
• Trees of tangles in abstract separation systems
• Obtaining trees of tangles from tangle-tree duality
• Profinite separation systems
• scientific article; zbMATH DE number 3865299 (Why is no real title available?)
• Abstract separation systems
• Trees of tangles in infinite separation systems

This page was built for publication: Structural submodularity and tangles in abstract separation systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2318482)