Knaster – Kuratowski – Mazurkiewicz lemma - Knaster–Kuratowski–Mazurkiewicz lemma

The Knaster – Kuratowski – Mazurkiewicz lemma matematikaning asosiy natijasidir sobit nuqta nazariyasi tomonidan 1929 yilda nashr etilgan Knaster, Kuratovskiy va Mazurkievich.^[1]

KKM lemmasini isbotlash mumkin Sperner lemmasi va buni isbotlash uchun ishlatilishi mumkin Brouwerning sobit nuqtali teoremasi.

Bayonot

Ruxsat bering ${ displaystyle Delta _ {n-1}}$ bo'lish ${ displaystyle (n-1)}$- o'lchovli oddiy bilan n tepaliklar sifatida belgilangan ${ displaystyle 1, ldots, n}$.

A KKM qoplamasi to'plam sifatida aniqlanadi ${ displaystyle C_ {1}, ldots, C_ {n}}$ ning yopiq to'plamlar har qanday kishi uchun ${ displaystyle I subseteq {1, ldots, n }}$, qavariq korpus ga to'g'ri keladigan tepaliklarning ${ displaystyle I}$ bu yopiq tomonidan ${ displaystyle bigcup _ {i in I} C_ {i}}$.

KKM lemmasi buni aytadi KKM qoplamasi bo'sh bo'lmagan chorrahaga ega, ya'ni:

${ displaystyle bigcap _ {i = 1} ^ {n} C_ {i} neq emptyset.}$

Misol

Qachon ${ displaystyle n = 3}$, KKM lemmasi oddiylikni ko'rib chiqadi ${ displaystyle Delta _ {2}}$ bu uchburchak bo'lib, uning tepalari 1, 2 va 3 deb belgilanishi mumkin. Bizga uchta yopiq to'plam berilgan ${ displaystyle C_ {1}, C_ {2}, C_ {3}}$ shu kabi:

• ${ displaystyle C_ {1}}$ 1-tepalikni qoplaydi, ${ displaystyle C_ {2}}$ tepalik 2 ni qoplaydi, ${ displaystyle C_ {3}}$ 3-vertikalni qoplaydi.
• 12-chekka (1-vertikaldan 2-tepalikka qadar) to'plamlar bilan qoplangan ${ displaystyle C_ {1}}$ va ${ displaystyle C_ {2}}$, 23 chekka to'plamlar bilan qoplangan ${ displaystyle C_ {2}}$ va ${ displaystyle C_ {3}}$, chekka 31 to'plamlar bilan qoplangan ${ displaystyle C_ {3}}$ va ${ displaystyle C_ {1}}$.
• Uchala to'plamning birlashishi butun uchburchakni qamrab oladi

KKM lemmasida to'plamlar deyilgan ${ displaystyle C_ {1}, C_ {2}, C_ {3}}$ umumiy kamida bitta fikrga ega bo'ling.

KKM lemmasining talablarini qondiradigan qoplamaning misoli

Lemma o'ngdagi rasm bilan tasvirlangan, unda # 1 to'plam ko'k, # 2 to'plam qizil va # 3 to'siq yashil rangda. KKM talablari qondiriladi, chunki:

• Har bir tepalik o'ziga xos rang bilan qoplangan.
• Har bir chekka ikkita tepalikning ikkita rangi bilan qoplangan.
• Uchburchak uchta rang bilan qoplangan.

KKM lemmasi uchta rang bilan bir vaqtning o'zida yopilgan nuqta borligini ta'kidlaydi; rasmda bunday nuqta aniq ko'rinib turibdi.

E'tibor bering, barcha to'plamlar yopiq bo'lishi kerak, ya'ni ularning chegaralarini o'z ichiga oladi. Agar, masalan, qizil to'plam yopilmagan bo'lsa, unda markaziy nuqta faqat ko'k va yashil to'plamlarda joylashgan bo'lishi mumkin, va keyin barcha uchta to'plamlarning kesishishi bo'sh bo'lishi mumkin.

Ekvivalent natijalar

Uchta ekvivalent variantda keltirilgan bir nechta sobit nuqtali teoremalar mavjud: an algebraik topologiya variant, kombinatorial variant va to'plamni qoplovchi variant. Har bir variantni mutlaqo boshqacha dalillar yordamida alohida isbotlash mumkin, ammo har bir variantni o'z qatoridagi boshqa variantlarga qisqartirish mumkin. Bundan tashqari, yuqori satrdagi har bir natija xuddi shu ustundagi pastdagi natijadan chiqarilishi mumkin.^[2]

Umumlashtirish

Rainbow KKM lemma (Gale)

Devid Geyl KKM lemmasining quyidagi umumlashtirilishini isbotladi.^[3] Deylik, bitta KKM qoplamasi o'rniga bizda bor n turli xil KKM qoplamalari: ${ displaystyle C_ {1} ^ {1}, ldots, C_ {n} ^ {1}, ldots, C_ {1} ^ {n}, ldots, C_ {n} ^ {n}}$. So'ngra, almashtirish mavjud ${ displaystyle pi}$ bo'sh bo'lmagan kesishgan qoplamalar, ya'ni:

${ displaystyle bigcap _ {i = 1} ^ {n} C_ {i} ^ { pi (i)} neq emptyset}$.

"Kamalak KKM lemma" nomi Geylning lemmasini ta'riflashidan ilhomlangan:

"Ushbu natijaning nutqiy bayonoti ... agar har uch kishining uchburchagi KKM qoidalariga binoan qizil, oq va ko'k ranglarni bo'yashsa, u holda bitta odamning qizil to'plamida joylashgan nuqta bo'ladi. boshqasi, uchinchisining ko'k ".^[3]

Kamalak KKM lemmasini a yordamida isbotlash mumkin Sperner lemmasining kamalak umumlashtirilishi.^[4]

Original KKM lemmasi oddiygina terib olish orqali kamalak KKM lemmasidan kelib chiqadi n bir xil qoplamalar.

Ulagichsiz lemma (Bapat)

Bapat tomonidan umumlashtirilgan KKM lemmasining tasviri

A ulagich oddiy simvol a ulangan to'plam bu barchaga tegadi n oddiy odamning yuzlari.

A ulagichsiz qoplama qoplama ${ displaystyle C_ {1}, ldots, C_ {n}}$ unda yo'q ${ displaystyle C_ {i}}$ ulagichni o'z ichiga oladi.

Har qanday KKM qoplamasi ulagichsiz qoplama hisoblanadi, chunki KKM qoplamasida yo'q ${ displaystyle C_ {i}}$ hatto barchasiga tegadi n yuzlar. Shu bilan birga, KKM qoplamasi bo'lmagan ulagichsiz qoplamalar mavjud. Bir misol o'ng tomonda tasvirlangan. U erda qizil to'plam uchta yuzga tegadi, lekin u hech qanday ulagichni o'z ichiga olmaydi, chunki uning hech qanday bog'langan komponenti uchta yuzga tegmaydi.

Teoremasi Ravindra Bapat, umumlashtiruvchi Sperner lemmasi,^{[5]:16-bob, 257-261-betlar} shuni anglatadiki, KKM lemmasi konnektorsiz qoplamalargacha tarqaladi (u o'zining teoremasini isbotladi ${ displaystyle n = 3}$).

Ulagichsiz variantda shuningdek, ikkala ushbu umumlashmalar bir vaqtning o'zida ishlatilishi uchun almashtirish varianti mavjud.

KKMS teoremasi

The KKMS teoremasi tomonidan KKM lemmasining umumlashtirilishi Lloyd Shapli. Bu foydali iqtisodiyot, ayniqsa kooperativ o'yin nazariyasi.^[6]

KKM qoplamasi o'z ichiga oladi n yopiq to'plamlar, a KKMS qoplamasi o'z ichiga oladi ${ displaystyle 2 ^ {n} -1}$ yopiq to'plamlar - ning bo'sh bo'lmagan to'plamlari bilan indekslangan ${ displaystyle [n]}$ (ekvivalent sifatida: bo'sh bo'lmagan yuzlar tomonidan ${ displaystyle Delta _ {n-1}}$). Har qanday kishi uchun ${ displaystyle I subseteq [n]}$, qavariq korpus ga to'g'ri keladigan tepaliklarning ${ displaystyle I}$ bo'lishi kerak yopiq ning pastki to'plamlariga mos keladigan to'plamlar birlashmasi tomonidan ${ displaystyle I}$ , anavi:

${ displaystyle operatorname {conv} ( {v_ {i}: i in I }) subseteq bigcup _ {J subseteq I} C_ {J}}$.

KKMS teoremasi, har qanday KKMS qoplamasi uchun a mavjudligini aytadi muvozanatli to'plam ${ displaystyle B}$ ning ${ displaystyle 2 ^ {[n]}}$, shunday qilib to'plamlar kesishmasi indekslanadi ${ displaystyle B}$ bo'sh emas:^[7]

${ displaystyle bigcap _ {J in B} C_ {J} neq emptyset}$

"Balansli to'plam" nima ekanligini tushuntirish qoladi. To'plam ${ displaystyle B}$ ning pastki to'plamlari ${ displaystyle [n]}$ deyiladi muvozanatli agar vazn funktsiyasi mavjud bo'lsa ${ displaystyle B}$ (vazn belgilash ${ displaystyle w_ {J} geq 0}$ hammaga ${ displaystyle J in B}$), shuning uchun har bir element uchun ${ displaystyle i in [n]}$, o'z ichiga olgan barcha kichik to'plamlarning og'irliklari yig'indisi ${ displaystyle i}$ aniq 1. Masalan, faraz qilaylik ${ displaystyle n = 3}$. Keyin:

• {{1}, {2}, {3}} to'plami muvozanatli: barcha og'irliklarni 1 ga teng qilib tanlang. Har bir element to'liq bir marta paydo bo'lgan har qanday to'plam uchun ham xuddi shunday, masalan, {{1,2} to'plam , {3}} yoki to'plam {{1,2,3}}.
• {{1,2}, {2,3}, {3,1}} to'plami muvozanatli: barcha vaznlarning 1/2 qismini tanlang. Xuddi shu narsa har bir element to'liq ikki marta paydo bo'lgan har qanday to'plam uchun ham amal qiladi.
• {{1,2}, {2,3}} to'plami muvozanatli emas, chunki har qanday ijobiy og'irlik tanlovi uchun 2-element yig'indisi 1 yoki 3-element yig'indisidan katta bo'ladi, shuning uchun buning iloji yo'q barcha summalar 1 ga teng.
• {{1,2}, {2,3}, {1}} to'plami muvozanatli: tanlang ${ displaystyle w_ {1,2} = 0, w_ {2,3} = 1, w_ {1} = 1}$.

Yilda gipergrafiya terminologiyasi, to'plam B uning asosiga nisbatan muvozanatli V, agar gipergraf vertex bilan o'rnatilgan bo'lsa V va chekka o'rnatilgan B mukammal fraksiyonel mosligini tan oladi.

KKMS teoremasi KKM lemmasini nazarda tutadi.^[7] Aytaylik, bizda KKM qoplamasi bor ${ displaystyle C_ {i}}$, uchun ${ displaystyle i = 1, ldots, n}$. KKMS qoplamasini qurish ${ displaystyle C '_ {J}}$ quyidagicha:

• ${ displaystyle C '_ {J} = C_ {i}}$ har doim ${ displaystyle J = {i }}$ (${ displaystyle J}$ faqat elementni o'z ichiga olgan singleton ${ displaystyle i}$).
• ${ displaystyle C '_ {J} = emptyset}$ aks holda.

Asl qoplamadagi KKM holati ${ displaystyle C_ {i}}$ yangi qoplamada KKMS holatini nazarda tutadi ${ displaystyle C '_ {J}}$. Shu sababli, yangi qoplamadagi mos keladigan to'plamlar bo'shashmasdan kesishgan bo'lishi uchun muvozanatli to'plam mavjud. Faqatgina mumkin bo'lgan muvozanatli to'plam - bu barcha singletonlar to'plamidir; shuning uchun asl qoplama bo'sh joysiz kesishgan.

KKMS teoremasi turli xil dalillarga ega.^[8][9][10]

Reni va Vuders muvozanatli to'plam ham tanlanishi mumkinligini isbotladilar sherik.^[11]

Chjou qoplama iborat bo'lgan KKMS teoremasining bir variantini isbotladi ochiq to'plamlar yopiq to'plamlardan ko'ra.^[12]

Polytopal KKMS teoremasi (Komiya)

Hidetoshi Komiya KKMS teoremasini soddaliklardan to umumlashtirdi polytopes.^[9] Ruxsat bering P har qanday ixcham konveks politop bo'ling. Ruxsat bering ${ displaystyle { textrm {Yuzlar}} (P)}$ bo'sh bo'lmagan yuzlar to'plami bo'ling P. A Komiya qoplamasi ning P yopiq to'plamlar oilasi ${ displaystyle {C_ {F}: F in { textrm {Faces}} (P) }}$ shunday qilib har bir yuz uchun ${ displaystyle F in { textrm {Faces}} (P)}$:

${ displaystyle F subseteq bigcup _ {G subseteq F, ~ G in { textrm {Faces}} (P)} C_ {G}}$.

Komiya teoremasi shuni aytadiki, har bir Komiya qoplamasi uchun Pbor muvozanatli to'plam ${ displaystyle B subseteq { textrm {Yuzlar}} (P)}$, shunday qilib to'plamlar kesishmasi indekslanadi ${ displaystyle B}$ bo'sh emas:^[7]

${ displaystyle bigcap _ {F in B} C_ {F} neq emptyset}$

Komiya teoremasi muvozanatli to'plamning ta'rifini ham umumlashtiradi: vazn funktsiyasi mavjudligini talab qilish o'rniga ${ displaystyle B}$ har bir vertikal yaqinidagi og'irliklar yig'indisi P 1 ga teng, biz har qanday ochkolar to'plamini tanlashdan boshlaymiz ${ displaystyle { textbf {b}} = {b ^ {F}: F in { textrm {Faces}} (P), b ^ {F} in F }}$. To'plam ${ displaystyle B subseteq { textrm {Yuzlar}} (P)}$ deyiladi muvozanatli munosabat bilan ${ displaystyle { textbf {b}}}$ iff ${ displaystyle b ^ {P} in operatorname {conv} {b ^ {F}: F in B }}$, ya'ni butun ko'pburchakka berilgan nuqta P a qavariq birikma to'plamdagi yuzlarga berilgan ballarning B.

KKMS teoremasi - bu Komiya teoremasining alohida hodisasi bo'lib, unda politop mavjud ${ displaystyle P = Delta _ {n-1}}$ va ${ displaystyle b ^ {F}}$ bo'ladi bariyenter yuzning F (xususan, ${ displaystyle b ^ {P}}$ ning bariyentridir ${ displaystyle Delta _ {n-1}}$, bu nuqta ${ displaystyle (1 / n, ldots, 1 / n)}$ ).

Chegara shartlari (Musin)

Oleg R. Musin KKM lemmasi va KKMS teoremasining bir necha umumlashmalarini isbotladi, ularning qoplamalarida chegara shartlari mavjud edi. Chegara shartlari bilan bog'liq homotopiya.^[13][14]

Adabiyotlar

Tashqi havolalar

• KKM Lemma-ning dalillarini ko'ring Sayyora matematikasi.