Structural submodularity and tangles in abstract separation systems

DOI10.1016/J.JCTA.2019.05.001zbMATH Open1417.05162arXiv1805.01439OpenAlexW2962864735WikidataQ127874634 ScholiaQ127874634MaRDI QIDQ2318482FDOQ2318482

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)

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.

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

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

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)

Cites Work

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

Cited In (9)

• Trees of tangles in infinite separation systems
• Tangle-tree duality in abstract separation systems
• Abstract separation systems
• Trees of tangles in abstract separation systems
• Refining trees of tangles in abstract separation systems: inessential parts
• Profinite separation systems
• A canonical tree-of-tangles theorem for structurally submodular separation systems
• Obtaining trees of tangles from tangle-tree duality
• Title not available (Why is that?)

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)