Tangle-tree duality in abstract separation systems

Cited 1 time in webofscience Cited 0 time in scopus
  • Hit : 74
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorDiestel, Reinhardko
dc.contributor.authorOum, Sang-ilko
dc.date.accessioned2021-01-28T05:52:09Z-
dc.date.available2021-01-28T05:52:09Z-
dc.date.created2020-12-04-
dc.date.issued2021-01-
dc.identifier.citationADVANCES IN MATHEMATICS, v.377, pp.107470-
dc.identifier.issn0001-8708-
dc.identifier.urihttp://hdl.handle.net/10203/280023-
dc.description.abstractWe prove a general width duality theorem for combinatorial structures with well-defined notions of cohesion and separation. These might be graphs or matroids, but can be much more general or quite different. The theorem asserts a duality between the existence of high cohesion 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 k-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.-
dc.languageEnglish-
dc.publisherACADEMIC PRESS INC ELSEVIER SCIENCE-
dc.titleTangle-tree duality in abstract separation systems-
dc.typeArticle-
dc.identifier.wosid000601332900020-
dc.identifier.scopusid2-s2.0-85095872726-
dc.type.rimsART-
dc.citation.volume377-
dc.citation.beginningpage107470-
dc.citation.publicationnameADVANCES IN MATHEMATICS-
dc.identifier.doi10.1016/j.aim.2020.107470-
dc.contributor.localauthorOum, Sang-il-
dc.contributor.nonIdAuthorDiestel, Reinhard-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorTangle-
dc.subject.keywordAuthorGraph minor-
dc.subject.keywordAuthorTree-decomposition-
dc.subject.keywordAuthorTangle-tree duality-
dc.subject.keywordAuthorSeparation-
dc.subject.keywordAuthorWidth parameter-
dc.subject.keywordPlusGRAPH MINORS-
dc.subject.keywordPlusDECOMPOSITION-
dc.subject.keywordPlusOBSTRUCTIONS-
dc.subject.keywordPlusCONNECTIVITY-
dc.subject.keywordPlusBLOCKS-
dc.subject.keywordPlusSETS-
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 1 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0