[논문]Tangle-tree duality in abstract separation systems

Diestel, Reinhard; Oum, Sang-il

doi:10.1016/j.aim.2020.107470

[해외논문] Tangle-tree duality in abstract separation systems 원문보기

Advances in mathematics, v.377, 2021년, pp.107470 -

Diestel, Reinhard (Mathematisches Seminar, Universitä) , Oum, Sang-il (t Hamburg)

Abstract ▼ AI-Helper

Abstract We 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.

Keyword

참고문헌 (40)

Discrete Appl. Math. Amini 309 20 6000 2009 Submodular partition functions
N. Bowler, R. Diestel, F. Mazoit, Tangle-tree duality in infinite graphs and matroids, in preparation.
Bowler
Eur. J. Comb. Carmesin 58 2016 10.1016/j.ejc.2016.04.007 A short proof that every finite graph has a tree-decomposition displaying its tangles

상세보기
Carmesin
SIAM J. Discrete Math. Carmesin 28 1876 2014 10.1137/130923646 k-blocks: a connectivity invariant for graphs

상세보기
Combinatorica Carmesin 34 1 1 2014 10.1007/s00493-014-2898-5 Connectivity and tree structure in finite graphs

상세보기
Carmesin
Diestel
Diestel
Abh. Math. Semin. Univ. Hamb. Diestel 87 223 2017 10.1007/s12188-016-0163-0 Ends and tangles

상세보기
Diestel 2017 Graph Theory
Order Diestel 35 157 2018 10.1007/s11083-017-9424-5 Abstract separation systems

상세보기
Order Diestel 35 171 2018 10.1007/s11083-017-9425-4 Tree sets

상세보기
R. Diestel, Tangles: indirect clustering in the empirical sciences, in preparation.
Diestel
Diestel
Combinatorica Diestel 39 1 37 2019 10.1007/s00493-017-3595-y Profiles of separations: in graphs, matroids, and beyond

상세보기
Diestel
Diestel
Combinatorica Diestel 39 879 2019 10.1007/s00493-019-3798-5 Tangle-tree duality in graphs, matroids and beyond

상세보기
Diestel
Elbracht
C. Elbracht, J. Kneip, M. Teegen, Obtaining trees of tangles from tangle-tree duality, in preparation.
Elbracht
Elbracht
Adv. Comb. Elbracht 2020 Tangles are decided by weighted vertex sets
Erde
SIAM J. Discrete Math. Erde 31 1529 2017 10.1137/16M1059539 Refining a tree-decomposition which distinguishes tangles

상세보기
J. Comb. Theory, Ser. B Erde 130 114 2018 10.1016/j.jctb.2017.12.001 A unified treatment of linked and lean tree-decompositions

상세보기
J. Comb. Theory, Ser. B Geelen 96 560 2006 10.1016/j.jctb.2005.11.001 Obstructions to branch-decomposition of matroids

상세보기
Gollin
Kneip
Kneip
Eur. J. Comb. Lyaudet 31 3 681 2010 10.1016/j.ejc.2009.09.004 Partitions versus sets: a case of duality

상세보기
J. Comb. Theory, Ser. B Mader 25 74 1978 10.1016/S0095-8956(78)80012-4 Über n-fach zusammenhängende Eckenmengen in Graphen

상세보기
Reed 1997 Surveys in Combinatorics Tree width and tangles: a new connectivity measure and some applications
J. Comb. Theory, Ser. B Robertson 41 92 1986 10.1016/0095-8956(86)90030-4 Graph minors. V. Excluding a planar graph

상세보기
J. Comb. Theory, Ser. B Robertson 52 153 1991 10.1016/0095-8956(91)90061-N Graph minors. X. Obstructions to tree-decomposition

상세보기
J. Comb. Theory, Ser. B Robertson 89 43 2003 10.1016/S0095-8956(03)00042-X Graph minors. XVI. Excluding a non-planar graph

상세보기

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

원문 보기

AccessON 원문보기

원문 URL 링크

DOI : 10.1016/j.aim.2020.107470
Elsevier : 저널 > 논문
AccessON : 저널

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

오픈액세스(OA) 유형

GREEN

저자가 공개 리포지터리에 출판본, post-print, 또는 pre-print를 셀프 아카이빙 하여 자유로운 이용이 가능한 논문

저작권 관리 안내

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

Text(ASCII format)
Excel format
RefWorks Direct Export
RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증