크나스테르-쿠라토프스키-마주르키에비치 덮개

수학에서 크나스테르-쿠라토프스키-마주르키에비치 덮개(Knaster-Kuratowski-Mazurkiewicz덮개, 영어: Knaster–Kuratowski–Mazurkiewicz cover)는 특정한 조건을 만족시키는, 단체의 닫힌집합으로 구성된 덮개이다. 구체적으로, 단체의 (꼭짓점의 부분 집합의 볼록 폐포인) 부분 단체는 각 꼭짓점에 대응되는 닫힌집합들로 덮혀져야 한다. 크나스테르-쿠라토프스키-마주르키에비치 정리(Knaster-Kuratowski-Mazurkiewicz定理, 영어: Knaster–Kuratowski–Mazurkiewicz theorem)에 따르면, 모든 크나스테르-쿠라토프스키-마주르키에비치 덮개는 적어도 하나 이상의 점을 공유한다 (즉, 그 교집합은 공집합이 될 수 없다).

${\displaystyle n+1}$개의 꼭짓점을 갖는 ${\displaystyle n}$차원 단체 ${\displaystyle \triangle ^{n}\subseteq \mathbb {R} ^{n}}$을 생각하고, 그 꼭짓점들의 집합을

${\displaystyle V\subseteq \triangle ^{n}}$

${\displaystyle |{\mathcal {V}}|=n+1}$

이라고 하자.

만약 ${\displaystyle \triangle ^{n}}$ 속의, ${\displaystyle n+1}$개 집합으로 구성된 집합족

${\displaystyle \{C_{v}\}_{v\in V}\subseteq \operatorname {Pow} (\triangle ^{n})}$

이 다음 두 조건을 만족시킨다면, 이를 크나스테르-쿠라토프스키-마주르키에비치 덮개라고 한다.

• 임의의 ${\displaystyle v\in V}$에 대하여, ${\displaystyle C_{v}}$는 닫힌집합이다.
• 임의의 꼭짓점의 집합 ${\displaystyle I\subseteq V}$에 대하여, ${\displaystyle \{C_{v}\}_{v\in I}}$는 ${\displaystyle I}$의 볼록 폐포에 해당하는 ${\displaystyle |I|-1}$차원 단체 ${\displaystyle \operatorname {Conv} (I)}$의 덮개를 이룬다. 즉, ${\displaystyle \textstyle \bigcup _{v\in I}C_{i}\supseteq \operatorname {Conv} (I)}$이다.

둘째 조건에서, ${\displaystyle I=V}$인 경우에 의하여, ${\displaystyle \{C_{v}\}_{v\in V}}$는 ${\displaystyle \triangle ^{n}}$의 덮개를 이루어야 한다. 마찬가지로, ${\displaystyle |I|=1}$인 경우에 의하여, 임의의 ${\displaystyle v\in V}$에 대하여 항상 ${\displaystyle v\in C_{v}}$이다.

크나스테르-쿠라토프스키-마주르키에비치 정리에 따르면, ${\displaystyle n\geq 0}$일 때, 모든 크나스테르-쿠라토프스키-마주르키에비치 덮개의 교집합은 절대로 공집합이 될 수 없다 (즉, ${\displaystyle \textstyle \bigcap _{v\in V}C_{v}\neq \varnothing }$).

보다 일반적으로, ${\displaystyle \triangle ^{n}}$ 위의, ${\displaystyle n+1}$개의 서로 다른 크나스테르-쿠라토프스키-마주르키에비치 덮개가 주어졌다고 하자. 즉, 집합족

${\displaystyle \{C_{u,v}\}_{(u,v)\in V^{2}}\subseteq \operatorname {Pow} (\triangle ^{n})}$

에서, 각 ${\displaystyle u\in V}$에 대하여

${\displaystyle \{C_{u,v}\}_{v\in V}}$

가 크나스테르-쿠라토프스키-마주르키에비치 덮개를 이룬다고 하자. 그렇다면, 다음 조건을 만족시키는 순열 ${\displaystyle \sigma \in \operatorname {Sym} (V)}$이 존재한다.^[1]

${\displaystyle \bigcap _{v\in V}C_{\sigma (v),v}\neq \varnothing }$

${\displaystyle n=2}$일 때, 2차원 단체 (즉, 삼각형) ${\displaystyle \triangle ^{2}}$의 다음과 같은 크나스테르-쿠라토프스키-마주르키에비치 덮개를 생각하자.

즉,

• 붉은 집합 · 푸른 집합 · 녹색 집합의 합집합은 삼각형의 닫힌 덮개를 이룬다.
• 붉은 집합 · 녹색 집합은 수직 변의 닫힌 덮개를 이룬다.
• 붉은 집합 · 푸른 집합은 수평 변의 닫힌 덮개를 이룬다.
• 녹색 집합 · 푸른 집합은 대각 변의 닫힌 덮개를 이룬다.
• 붉은 집합 · 푸른 집합 · 녹색 집합은 각각 한 꼭짓점을 포함한다.

이 경우, 크나스테르-쿠라토프스키-마주르키에비치 정리에 따라 붉은 집합 · 푸른 집합 · 녹색 집합은 한 점을 공유하며, 이는 삼각형 가운데의, 세 집합이 맞닿는 점이다.

브로니스와프 크나스테르(폴란드어: Bronisław Knaster) · 카지미에시 쿠라토프스키 · 스테판 마주르키에비치가 1929년에 이 조건 및 크나스테르-쿠라토프스키-마주르키에비치 정리를 증명하였다.^[2]

복수의 크나스테르-쿠라토프스키-마주르키에비치 덮개에 대한 크나스테르-쿠라토프스키-마주르키에비치 정리의 일반화는 데이비드 게일(영어: David Gale, 1921~2008)이 1984년에 증명하였다.^[1]

• Rosenzweig, Matthew H. (2012년 9월). “Knaster-Kuratowski-Mazurkiewicz (KKM) theorem” (PDF) (영어). 2021년 5월 7일에 원본 문서 (PDF)에서 보존된 문서. 2018년 3월 6일에 확인함.