Guest닫기

상세내용

상세 정보
서명 / 저자 On fractional Helly properties in graphs without large complete minors = 큰 완전 그래프를 마이너로 가지지 않는 그래프에서의 fractional Helly 성질에 관하여 / Kim, Minki.
저자명 Kim, Minki ; 김민기
발행사항 [대전 : 한국과학기술원, 2018].
online access
Online Access /thesis_pdf_02/2018/2018D02014...  원문
서가 정보
등록번호 소장위치/청구기호 도서상태
8032657 학술문화관(도서관)2층 패컬티라운지(학위논문)
DMAS 18011  
이용가능
대출가능확인

Helly 정리는 유클리드 공간에서의 볼록집합들의 교차 패턴에 관한 고전적인 결과로 $R^d$의 유한한 개수의 볼록집합들이 주어져 있을 때 d+1 혹은 그 이하의 개수의 볼록집합들마다 교차하면 모든 몰록집합들이 교차한다는 내용을 말한다. 지난 수십 년간 Helly 정리의 일반화와 응용에 대한 연구가 진행되었는데 그 중에서도 중요한 일반화로 colorful Helly 정리, fractional Helly 정리, (p,q)-정리 등이 있다. 특히 fractional Helly 성질은 추상적인 집합계에서의 (p,q)-정리를 증명하는 데에 핵심 역할을 한다고 알려짐에 따라 fractional Helly 성질을 가지기 위한 충분조건을 찾는 것은 이 분야에서 가장 기본적인 질문으로 제시되고 있다. 본 학위논문에서는 Helly형 정리들에 대한 개요를 설명하고 최근 증명한 Helly 정리의 조합적인 일반화들을 소개하고자 한다. 본 논문의 첫 주제는 colorful Helly 정리와 fractional Helly 정리의 융합이다. 볼록집합들의 모임에 대한 기존의 colorful fractional Helly 정리의 결과를 향상시킬 수 있는 순수 조합적인 방법을 소개하고 이를 이용하여 볼록집합들의 모임 및 추상적인 집합계에 대한 colorful fractional Helly 정리들을 증명하였다. 두 번째 주제는 교집합이 연결된 그래프인 그래프들의 모임에 대한 Helly형 정리들이다. 주어진 그래프 $G$에 대하여 모든 교집합이 연결된 그래프인 유도된 부분 그래프들의 모임을 connected cover라고 정의하며 본 논문에서는 fractional Helly 성질에 중점을 두고 큰 완전 그래프를 마이너로 가지지 않는 그래프에서의 connected cover들에 대한 Helly형 정리들을 증명하였다. 특히 평면 그래프에서의 connected cover에 대한 결과들은 평면 위의 good cover보다 더 일반적인 집합계에 대해 적용할 수 있다.
한줄서평
입력된 한줄서평이 없습니다.