Tangle-tree duality:in graphs, matroids and beyond

Link:
Autor/in:
Erscheinungsjahr:
2019
Medientyp:
Text
Schlagworte:
  • math.CO
  • 05C83, 05C40, 05C05
Beschreibung:
  • 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.
Lizenz:
  • info:eu-repo/semantics/closedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/01d99232-4786-44ae-86e5-2d6309818ae3