Knaster–Kuratowski–Mazurkiewicz lemma

Knaster –Kuratowski–Mazurkiewicz-lemmat är ett grundläggande resultat i matematisk fixpunktsteori som publicerades 1929 av Knaster , Kuratowski och Mazurkiewicz .

KKM-lemmat kan bevisas från Sperners lemma och kan användas för att bevisa Brouwers fixpunktssats .

Påstående

Låt $\Delta _{n-1}$ vara en $(n-1)$ -dimensionell simplex med n hörn märkta som $1 ,\ldots ,n$ .

En KKM-beläggning definieras som en uppsättning $C_{1},\ldots ,C_{n}$ av slutna uppsättningar så att för alla $I\subseteq \{1,\ldots ,n\}$ , det konvexa skrovet på hörnen som motsvarar $I$ täcks av $\bigcup _{i\in I} C_{i}$ .

KKM-lemmat säger att i varje KKM-beläggning är den gemensamma skärningspunkten för alla n uppsättningar icke-tom , dvs.

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

Exempel

När $n=3$ , betraktar KKM-lemmat simplexet $\Delta _{2}$ som är en triangel, vars hörn kan betecknas 1, 2 och 3. Vi får tre slutna uppsättningar $C_{1},C_{2},C_{3}$ så att:

• $C_{1}$ täcker vertex 1, $C_{2}$ täcker vertex 2, $C_{3}$ täcker vertex 3.
• Kanten 12 (från vertex 1 till vertex 2) täcks av uppsättningarna $C_{1}$ och $C_{2}$ , kanten 23 täcks av uppsättningarna ${\ displaystyle C_{2}}$ och $C_{3}$ , kanten 31 täcks av uppsättningarna $C_{3}$ och $C_{1}$ .
• Föreningen av alla tre uppsättningarna täcker hela triangeln

KKM-lemmat anger att mängderna $C_{1},C_{2},C_{3}$ har minst en punkt gemensam.

Ett exempel på en täckning som uppfyller kraven i KKM-lemmat

Lemmat illustreras av bilden till höger, där set #1 är blått, set #2 är rött och set #3 är grönt. KKM-kraven är uppfyllda, eftersom:

• Varje vertex är täckt av en unik färg.
• Varje kant är täckt av de två färgerna på dess två hörn.
• Triangeln täcks av alla tre färgerna.

KKM-lemmat anger att det finns en punkt som täcks av alla tre färgerna samtidigt; en sådan punkt syns tydligt på bilden.

Observera att det är viktigt att alla uppsättningar är stängda, dvs innehåller sin gräns. Om till exempel den röda uppsättningen inte är stängd, är det möjligt att den centrala punkten endast finns i de blå och gröna uppsättningarna, och då kan skärningspunkten mellan alla tre uppsättningarna vara tom.

Motsvarande resultat

Det finns flera fixpunktssatser som finns i tre ekvivalenta varianter: en algebraisk topologivariant , en kombinatorisk variant och en mängdtäckande variant. Varje variant kan bevisas separat med helt olika argument, men varje variant kan också reduceras till de andra varianterna i sin rad. Dessutom kan varje resultat i den översta raden härledas från det under det i samma kolumn.

Algebraisk topologi	Kombinatorik	Set täckning
Brouwers fixpunktssats	Sperners lemma	Knaster–Kuratowski–Mazurkiewicz lemma
Borsuk–Ulams teorem	Tuckers lemma	Lusternik–Schnirelmanns sats

Generaliseringar

Rainbow KKM lemma (Gale)

David Gale bevisade följande generalisering av KKM-lemmat. Antag att vi istället för en KKM-beläggning har n olika KKM-beläggningar: $C_{1}^{1},\ ldots ,C_{n}^{1},\ldots,C_{1}^{n},\ldots ,C_{n}^{n}$ . Sedan finns det en permutation $\pi$ av beläggningarna med en icke-tom skärningspunkt, dvs:

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

Namnet "rainbow KKM lemma" är inspirerat av Gales beskrivning av hans lemma:

"Ett vardagligt uttalande av detta resultat är... om var och en av tre personer målar en triangel röd, vit och blå enligt KKM-reglerna, kommer det att finnas en punkt som är i den röda uppsättningen av en person, den vita uppsättningen av en annan, den tredjes blå".

Regnbågs KKM-lemma kan bevisas med en regnbågsgeneralisering av Sperners lemma .

Det ursprungliga KKM-lemmat följer från regnbågs-KKM-lemmat genom att helt enkelt välja n identiska beläggningar.

Anslutningsfritt lemma (Bapat)

En illustration av det generaliserade KKM-lemmat av Bapat

En koppling av en simplex är en ansluten uppsättning som berör alla n ytor av simplexen.

Ett kopplingsfritt hölje är ett hölje $C_{1},\ldots ,C_{n}$ där ingen $C_{i}$ innehåller en koppling.

Alla KKM-beläggningar är en kopplingsfria beläggningar, eftersom i en KKM-beläggning, ingen $C_{i}$ ens vidrör alla n ansikten. Det finns dock kopplingsfria beläggningar som inte är KKM-beläggningar. Ett exempel illustreras till höger. Där berör den röda uppsättningen alla tre ytorna, men den innehåller ingen kontakt, eftersom ingen ansluten komponent i den berör alla tre ytorna.

En sats av Ravindra Bapat , som generaliserar Sperners lemma , antyder att KKM-lemmat sträcker sig till kopplingsfria beläggningar (han bevisade sin sats för ${\displaystyle n=3})$ .

Den kopplingsfria varianten har även en permutationsvariant, så att båda dessa generaliseringar kan användas samtidigt.

KKMS-sats

KKMS -satsen är en generalisering av KKM-lemmat av Lloyd Shapley . Det är användbart inom ekonomi , särskilt inom kooperativ spelteori .

Medan en KKM-beläggning innehåller n slutna uppsättningar, innehåller en KKMS-beläggning $2^{n}-1$ slutna uppsättningar - indexerade av de icke-tomma delmängderna av $[n]$ (motsvarande: av icke-tomma ytor av ${\displaystyle \Delta _{n-1}} )$ . För alla ${\displaystyle I\subseteq [n]} ,$ bör det konvexa skrovet på hörnen som motsvarar $I$ täckas av föreningen av mängder som motsvarar delmängder av $I$ , det är:

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

Varje KKM-beläggning är ett specialfall av en KKMS-beläggning. I en KKM-beläggning är de n uppsättningarna som motsvarar singletons icke tomma, medan de andra uppsättningarna är tomma. Det finns dock många andra KKMS-beläggningar.

i allmänhet är det inte sant att den gemensamma skärningspunkten för alla $2^{n}-1$ uppsättningar i en KKMS-beläggning inte är tom; detta illustreras av specialfallet med en KKM-beläggning, där de flesta set är tomma.

KKMS-satsen säger att det i varje KKMS-beläggning finns en balanserad samling $B$ av $2^{[n]}$ , så att skärningen av mängder indexerade med ${\ displaystyle B}$ är icke-tom :

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

Det återstår att förklara vad en "balanserad samling" är. En samling $B$ av delmängder av $[n]$ kallas balanserad om det finns en viktfunktion på $B$ (tilldelar en vikt $w_{J }\geq 0$ till varje $J\in B$ ), så att, för varje element $i\in [n]$ , summan av vikterna av alla delmängder som innehåller $i$ är exakt 1. Anta till exempel $n=3$ . Sedan:

• Samlingen {{1}, {2}, {3}} är balanserad: välj att alla vikter ska vara 1. Detsamma gäller för alla samlingar där varje element förekommer exakt en gång, till exempel samlingen {{1,2} ,{3}} eller samlingen { {1,2,3} }.
• Samlingen {{1,2}, {2,3}, {3,1}} är balanserad: välj att alla vikter ska vara 1/2. Detsamma gäller för alla samlingar där varje element förekommer exakt två gånger.
• Samlingen {{1,2}, {2,3}} är inte balanserad, eftersom för alla val av positiva vikter kommer summan för element 2 att vara större än summan för element 1 eller 3, så det är inte möjligt att alla summor är lika med 1.
• Samlingen {{1,2}, {2,3}, {1}} är balanserad: välj $w_{1,2}= 0,w_{2,3}=1,w_{1}=1$ .

I hypergrafterminologi är en samling B balanserad med avseende på dess markuppsättning V , om hypergrafen med vertexuppsättning V och kantuppsättning B medger en perfekt bråkmatchning.

KKMS-satsen antyder KKM-lemmat. Antag att vi har en KKM som täcker $C_{i}$ , för $i=1,\ldots ,n$ . Konstruera ett KKMS som täcker $C'_{J}$ enligt följande:

• $C'_{J}=C_{i}$ närhelst $J=\{i\}$ ( $J$ är en singelton som innehåller endast element $i$ ).
• $C'_{J}=\emptyset$ annars.

KKM-tillståndet på det ursprungliga höljet $C_{i}$ innebär KKMS-villkoret på det nya höljet $C'_{J}$ . Därför finns det en balanserad samling så att motsvarande uppsättningar i den nya täckningen har en icke-tom skärningspunkt. Men den enda möjliga balanserade samlingen är insamlingen av alla singlar; därför har den ursprungliga täckningen en icke-tom skärningspunkt.

KKMS-satsen har olika bevis.

Reny och Wooders bevisade att det balanserade setet också kan väljas som partner .

Zhou bevisade en variant av KKMS-satsen där täckningen består av öppna mängder snarare än slutna mängder.

Polytopal KKMS-sats (Komiya)

Hidetoshi Komiya generaliserade KKMS-satsen från förenklingar till polytoper . Låt P vara vilken kompakt konvex polytop som helst. Låt ${\textrm {Faces}}(P)$ vara uppsättningen av icke-tomma ansikten av P . En Komiya-beläggning av P är en familj av slutna uppsättningar $\{C_{F}:F\in {\textrm {Faces}}(P)\}$ så att för varje ansikte $F\in {\textrm {Faces}}(P)$ :

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

Komiyas sats säger att för varje Komiya-beläggning av P finns det en balanserad samling ${\displaystyle B\subseteq {\textrm {Faces}}(P)} ,$ så att skärningspunkten av mängder indexeras av ${ \displaystyle B}$ är inte tom:

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

Komiyas teorem generaliserar också definitionen av en balanserad samling: istället för att kräva att det finns en viktfunktion på $B$ så att summan av vikter nära varje vertex av P är 1, börjar vi med att välja valfri uppsättning punkter ${\textbf {b}}=\{b^{F}:F\in {\textrm {Faces}}(P), b^{F}\in F\}$ . En samling $B\subseteq {\textrm {Faces}}(P)$ kallas balanserad med avseende på ${\textbf {b}}$ iff ${\displaystyle b^{P}\in \operatorname {conv} \{b^{F}:F\in B\}} , det vill säga den$ punkt som är tilldelad hela polygonen P är en konvex kombination av de punkter som tilldelats ansiktena i samlingen B .

KKMS-satsen är ett specialfall av Komiyas sats där polytopen $P=\Delta _{n-1}$ och $b^{F}$ är barycentrum för ansiktet F (särskilt $b^{P}$ är barycentrum för $\Delta _{n-1}$ , vilket är punkten ${\displaystyle (1/n,\ldots ,1/n)} )$ .

Gränsförhållanden (Musin)

Oleg R. Musin bevisade flera generaliseringar av KKM-lemmat och KKMS-teoremet, med randvillkor på beläggningarna. Gränsvillkoren är relaterade till homotopi .

Se även

• En vanlig generalisering av KKMS-satsen och Carathéodorys sats .

externa länkar

• Se beviset på KKM Lemma i Planet Math .