헬리의 정리

헬리의 정리는 볼록 다각형의 교집합에 관한 이산 기하학의 기본적인 결과이다. 이것은 1913년에 에두아르트 헬리가 발견했다^[1]. 하지만 1923년까지는 그는 출판하지 않았고, 그 때는 이미 Radon (1921)와 König (1922)에 의해서 다른 증명이 나왔었다. 헬리의 정리는 헬리족의 개념을 제시했다.

명제 편집

$X 1, ..., X n$ 를 $n > d$ 인 $R d$ 의 볼록 부분집합의 유한한 집합이라고 하자. 만약 모든 이 집합의 원소 $d + 1$ 개의 교집합이 공집합이 아니라면, 전체 집합의 교집합도 공집합이 아니다;

\bigcap _{j=1}^{n}X_{j}\neq \varnothing .

무한한 집합에서는 콤팩트성을 가정해야 한다:

${X α}$ 를 $R d$ 의 콤팩트 볼록 부분집합의 집합이라고 가정하면, 크기가 $d + 1$ 인 모든 부분집합의 교집합이 공집합이 아니라고 하면, 전체 집합의 교집합도 공집합이 아니다.

증명 편집

Radon (1921)가 라돈의 정리를 통해서 유한한 경우를 증명했다. 그러면 무한한 경우는 콤팩트성의 유한 교집합 성질 특성화를 따른다: 콤팩트 공간의 닫힌 부분집합의 집합은 모든 유한한 부분집합의 교집합이 공집합이 아닐 때만 공집합이 아니다 (한번 한 집합을 고정하면, 그것을 포함하는 다른 모든 것들의 교집합은 고정한 콤팩트 공간의 닫힌 부분집합이다).

증명은 귀납법으로 이루어졌다:

기본적인 경우: $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$ 인 경우의 증명을 완성한다.

귀납적 단계: $n > d + 2$ 이고 $n -1$ 일 때 위의 명제가 참이라고 가정하자. 위의 증명은 어떤 집합 $d + 2$ 개의 부분집합의 교집합은 공집합이 아니라는 것을 보인다. 이제는 두 집합 $X n -1$ 과 $X n$ 을 하나의 집합 $X n -1 \cap X n$ 으로 바꾼 집합을 고려한다. 이 새로운 집합에서, 모든 집합 $d + 1$ 개의 부분집합의 교집합은 공집합이 아니다. 따라서 유도 가설이 적용되고, 이 새로운 집합의 교집합이 공집합이 아니라는 것을 보인다. 이것은 원래의 집합에 동일하게 적용되고, 증명을 완성한다.

같이 보기 편집

참조 편집

↑ Danzer, Grünbaum & Klee (1963).

Bollobás, B. (2006), 〈Problem 29, Intersecting Convex Sets: Helly's Theorem〉, 《The Art of Mathematics: Coffee Time in Memphis》, Cambridge University Press, 90–91쪽, ISBN 0-521-69395-0 .
Danzer, L.; Grünbaum, B.; Klee, V. (1963), 〈Helly's theorem and its relatives〉, 《Convexity》, Proc. Symp. Pure Math. 7, American Mathematical Society, 101–179쪽 .
Eckhoff, J. (1993), 〈Helly, Radon, and Carathéodory type theorems〉, 《Handbook of Convex Geometry》 A, B, Amsterdam: North-Holland, 389–448쪽 .
Heinrich Guggenheimer (1977) Applicable Geometry, page 137, Krieger, Huntington ISBN 0-88275-368-1 .
Helly, E. (1923), “Über Mengen konvexer Körper mit gemeinschaftlichen Punkten”, 《Jahresbericht der Deutschen Mathematiker-Vereinigung》 32: 175–176 .
König, D. (1922), “Über konvexe Körper”, 《Mathematische Zeitschrift》 14 (1): 208–220, doi:10.1007/BF01215899 .
Radon, J. (1921), “Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten”, 《Mathematische Annalen》 83 (1–2): 113–115, doi:10.1007/BF01464231 .

[1] Danzer, Grünbaum & Klee (1963).

[1]