헬리의 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 명제
- 2.1. 유한한 경우
- 2.2. 무한한 경우
3. 증명
- 3.1. 귀납법을 이용한 증명 (유한한 경우)
  - 3.1.1. 기본적인 경우
  - 3.1.2. 귀납적 단계
4. 확장된 정리
- 4.1. 다채로운 헬리 정리 (Colorful Helly theorem)
- 4.2. 분수 헬리 정리 (Fractional Helly theorem)
참조

1. 개요

헬리의 정리는 n > d일 때, d차원 공간 R^d의 볼록 부분집합 X₁, ..., X_n 중 임의의 d + 1개의 교집합이 공집합이 아니면, 전체 집합의 교집합도 공집합이 아니라는 정리이다. 무한 개의 집합에 대해서는 콤팩트성을 가정해야 한다. 이 정리는 수학적 귀납법과 라돈의 정리를 통해 증명되며, 다채로운 헬리 정리 및 분수 헬리 정리와 같은 확장된 형태로도 존재한다.

더 읽어볼만한 페이지

볼록기하학 정리 - 브라우어르 고정점 정리
브라우어르 고정점 정리는 콤팩트 볼록 집합에서 자기 자신으로 가는 연속 함수는 반드시 고정점을 가진다는 정리로, 다양한 공간에서 여러 형태로 표현되며 함수해석학에서 중요한 역할을 한다.
볼록기하학 정리 - 라돈의 정리
d차원 공간에서 d+2개의 점으로 이루어진 집합은 볼록 껍질이 교차하는 두 개의 부분집합으로 분할할 수 있다는 라돈의 정리는 헬리의 정리 증명에 사용될 뿐 아니라 VC 차원 계산과 중심점 근사 알고리즘 등 다양한 분야에 응용된다.
이산기하학 정리 - 라돈의 정리
d차원 공간에서 d+2개의 점으로 이루어진 집합은 볼록 껍질이 교차하는 두 개의 부분집합으로 분할할 수 있다는 라돈의 정리는 헬리의 정리 증명에 사용될 뿐 아니라 VC 차원 계산과 중심점 근사 알고리즘 등 다양한 분야에 응용된다.
이산기하학 정리 - 크레인-밀만 정리
크레인-밀만 정리는 함수 해석학에서 콤팩트 볼록 집합이 극점을 가지며, 하우스도르프 국소 볼록 공간에서 극점의 닫힌 볼록 폐포와 같다는 것을 보이는 정리로, 마르크 크레인과 다비드 밀만에 의해 증명되었다.

헬리의 정리
개요
분야	기하학
설명	d차원 공간에서 볼록 집합들의 교집합에 대한 정리 유한 개의 볼록 집합족이 있을 때, 전체 족의 교집합이 공집합이 아니기 위한 조건은 부분족의 교집합이 공집합이 아닌 것이다.
관련 개념	라돈의 정리 카라테오도리의 정리
응용 분야	조합론 계산 기하학 최적화
역사
제창자	에두아르트 헬리
발표 연도	1923년
관련 연구자	요한 라돈 데네스 코니그
공식 명칭 및 다른 이름
공식 명칭	헬리의 정리
다른 이름	헬리의 교차 정리 헬리족

2. 명제

''n'' > ''d''^영어일 때, 의 볼록 부분집합의 유한한 집합 에서 임의의 개의 교집합이 공집합이 아니라면, 전체 집합의 교집합도 공집합이 아니다. 무한한 집합에서는 콤팩트성을 가정해야 하는데, 의 콤팩트 볼록 부분집합의 집합 에서, 크기가 이하인 모든 부분집합의 교집합이 공집합이 아닐 경우, 전체 집합의 교집합도 공집합이 아니다.

2. 1. 유한한 경우

''n'' > ''d''^영어일 때, 의 볼록 부분집합 중 임의의 개의 교집합이 공집합이 아니면, 전체 집합의 교집합도 공집합이 아니다. 즉,

:

\bigcap_{j=1}^n X_j\ne\varnothing

이다.

2. 2. 무한한 경우

'''R'''^''d''^영어의 콤팩트 볼록 부분집합의 집합에서, 크기가 이하인 모든 부분집합의 교집합이 공집합이 아니면, 전체 집합의 교집합도 공집합이 아니다.

3. 증명

헬리의 정리는 수학적 귀납법을 사용하여 유한한 경우를 증명하고, 콤팩트 공간의 유한 교집합 성질을 이용하여 무한한 경우로 확장하여 증명할 수 있다.^[1]

먼저, 라돈의 정리를 사용하여 유한한 경우를 증명한다. 무한한 경우는 콤팩트성의 유한 교집합 성질 특성화를 통해 증명할 수 있는데, 이는 콤팩트 공간의 닫힌 부분집합의 집합에서 모든 유한한 부분집합의 교집합이 공집합이 아닐 때만 그 집합의 교집합이 공집합이 아니라는 성질이다.

구체적인 증명 과정은 수학적 귀납법을 따르며, 증명하고자 하는 식은 다음과 같다.

: $p\in\bigcap_{j=1}^n X_j.$

3. 1. 귀납법을 이용한 증명 (유한한 경우)

라돈의 정리를 이용해 유한한 경우를 증명할 수 있다.^[1] 증명은 수학적 귀납법으로 이루어진다.

기본적인 경우(

n=d+2

)에 대한 증명은 이미 하위 섹션에서 완료되었으므로, 여기서는

n>d+2

인 경우, 즉 귀납적 단계에 대한 증명을 간략하게 제시한다.

n>d+2

이고

n-1

일 때 명제가 참이라고 가정하면, 기본적인 경우의 증명에 의해

d+2

개 집합들의 부분집합의 교집합은 공집합이 아니다. 이제 두 집합

X_{n-1}

과

X_n

을 하나의 집합

X_{n-1} \cap X_n

으로 바꾼 집합을 고려한다. 이 새로운 집합에서 모든

d+1

개 부분집합의 교집합은 공집합이 아니므로, 귀납적 가설에 의해 이 새로운 집합의 교집합이 공집합이 아님을 보일 수 있다. 이는 원래 집합에도 동일하게 적용된다.

3. 1. 1. 기본적인 경우

Radon's theorem|라돈의 정리^영어를 이용하여

n=d+2

일 때, 즉 기본적인 경우를 증명할 수 있다.^[1]

증명은 수학적 귀납법으로 이루어진다.
기본적인 경우:

n=d+2

라고 가정하자. 그러면 가정에 의해 모든

j=1, ..., n

에 대해서

X_j

를 제외한 모든

X_i

의 공통 교집합의 점

x_j

가 존재한다.

이제

A = \{x_1, ..., x_n\}

에 라돈의 정리를 적용하면,

A

는

A_1

의 볼록 폐포가

A_2

의 볼록 폐포와 교차하는

A

의 서로소 부분집합

A_1, A_2

를 갖는다.

p

가 이 두 볼록 폐포의 교집합에 있는 점이라고 가정하면, 다음이 성립한다.

:

p\in\bigcap_{j=1}^n X_j.

이제, 어떤

j \in \{1, ..., n\}

에 대하여,

p \in X_j

임을 보일 수 있다.

X_j

에 있지 않을 수 있는

A

의 원소는

x_j

뿐이다. 만약

x_j \in A_1

이면,

x_j \notin A_2

이고, 따라서

X_j \supset A_2

이다.

X_j

가 볼록이기 때문에,

A_2

의 볼록 폐포를 포함하고 따라서

p \in X_j

이다. 비슷하게,

x_j \notin A_1

이면,

X_j \supset A_1

이고, 같은 추론으로

p \in X_j

이다.

p

가 모든

X_j

에 있기 때문에, 교집합에도 있어야 한다.

만약

x_1, ..., x_n

들이 모두 서로 다른 점이 아니라면, 즉 일부

i \neq k

에 대해서

x_i = x_k

라고 하면,

x_i

는 모든 집합

X_j

에 있게 되고, 따라서 교집합은 공집합이 아니라고 결론지을 수 있다.

이로써

n=d+2

인 경우, 즉 기본적인 경우의 증명이 완료된다.^[1]

3. 1. 2. 귀납적 단계

이고 일 때 명제가 참이라고 가정한다. 위의 증명에서 개의 집합의 부분집합들의 교집합은 공집합이 아니라는 것을 보였다. 이제 두 집합 과 을 하나의 집합 으로 바꾼 집합을 고려한다. 이 새로운 집합에서 모든 개의 부분집합의 교집합은 공집합이 아니다. 따라서 귀납적 가설이 적용되어 이 새로운 집합의 교집합이 공집합이 아니라는 것을 보인다. 이것은 원래의 집합에 동일하게 적용되고 증명이 완료된다.

4. 확장된 정리

헬리의 정리는 다양한 형태로 확장될 수 있다.

'''다채로운 헬리 정리''': '''R'''^''d''^영어의 볼록 부분 집합 ''d''+1개의 집합에 대한 헬리의 정리의 확장이다.
'''분수 헬리 정리''': 모든 ''a'' > 0에 대해 어떤 ''b'' > 0가 존재하여, 의 ''n''개의 볼록 부분집합 에서, 집합의 (''d''+1)-튜플 중 최소한 ''a''의 비율이 공통점을 갖는다면, 최소한 ''b''의 비율의 집합들이 공통점을 갖는다.

4. 1. 다채로운 헬리 정리 (Colorful Helly theorem)

'''다채로운 헬리 정리'''는 헬리의 정리의 확장으로, 단 하나의 집합 대신 '''R'''^''d''^영어의 볼록 부분 집합의 ''d''+1개의 집합이 있다.

만약, ''모든'' ''횡단'' 선택에 대해, 즉 각 집합에서 하나의 집합을 선택하는 것에 대해, 선택된 모든 집합에 공통된 점이 있다면, ''적어도 하나의'' 집합에 대해, 그 집합 내의 모든 집합에 공통된 점이 있다.

비유적으로, ''d''+1개의 집합을 ''d''+1개의 다른 색깔이라고 생각할 수 있다. 그러면 이 정리는 각 색깔별로 하나의 집합을 선택한 모든 선택이 비어 있지 않은 교차점을 가지면, 그 색깔의 모든 집합이 비어 있지 않은 교차점을 갖는 색깔이 존재한다고 말한다.^[2]

4. 2. 분수 헬리 정리 (Fractional Helly theorem)

모든 ''a'' > 0에 대해 어떤 ''b'' > 0가 존재하여, 의 ''n''개의 볼록 부분집합 에서, 집합의 (''d''+1)-튜플 중 최소한 ''a''의 비율이 공통점을 갖는다면, 최소한 ''b''의 비율의 집합들이 공통점을 갖는다.

참조

_[1] 서적 1963
_[2] 간행물 News on Fractional Helly, Colorful Helly, and Radon https://gilkalai.wor[...] 2020-07-13
_[3] 서적 1963
_[4] 서적 1963

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com