Tuckers Lemma

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 13. februar 2021; verifikation kræver 1 redigering .

Tuckers lemma  er en kombinatorisk analog til Borsuk-Ulam-sætningen , opkaldt efter Albert W. Tucker .

Essensen af ​​lemmaet er som følger:

Lad T være en triangulering af en lukket n -dimensional kugle . Antag, at T er antipodalsymmetrisk ved grænsen af ​​kuglen . Det betyder, at delmængden af ​​trianguleringssimpliceringer, der ligger på , danner en triangulering af kuglen , og hvis simpleksen σ hører til denne triangulering, så hører -σ også til den (for figuren til højre er simplicerne på cirklen buer, så betingelsen beskrevet ovenfor betyder, at for hver bue har en bue symmetrisk om midten af ​​cirklen).

Lade være mærkningen af ​​hjørnerne af trianguleringen T, der opfylder paritetsbetingelsen på , Det vil sige for enhver toppunkt . Derefter siger Tuckers lemma, at trianguleringen T indeholder en kant med modsatte etiketter , altså en kant (1-simplex), hvis hjørner er mærket med det samme tal, men med forskellige fortegn [1] .

Beviser

Det første bevis var ikke-konstruktivt (bevis ved modsigelse) [2] .

Senere blev der fundet et konstruktivt bevis, som er givet af en algoritme, der finder en kant med modsatte etiketter [3] [4] . Grundlæggende er algoritmer sti-baserede - de starter på et eller andet tidspunkt eller kanten af ​​trianguleringen og fortsætter fra simpleks til simpleks i henhold til foreskrevne regler, mens processen stadig er i gang. Det kan bevises, at stien skal ende på en simplex indeholdende en kant med modsatte etiketter.

Et simpelt bevis på Tuckers lemma bruger det mere generelle Ki Fans lemma , som har et simpelt algoritmisk bevis.

Den følgende beskrivelse illustrerer algoritmen for [5] . Bemærk, at der i dette tilfælde er en disk med 4 mulige etiketter: , som i figuren ovenfor.

Lad os starte uden for bolden og se på etiketterne på grænsen. Da etiketten er en ulige funktion på grænsen, skal grænsen indeholde positive og negative etiketter:

Lad os vælge en kant og gå igennem den. Der kan være tre tilfælde:

Vi kan ende uden for cirklen som følge heraf. Men da antallet af kanter på grænsen er ulige, skal der være en ny tidligere ubesøgt kant på skellet. Vi gennemgår det og fortsætter processen.

Rejsen skal ende inde i cirklen enten i simplex a eller i simplex . Q.E.D.

Åbningstider

Løbetiden for den beskrevne algoritme er polynomiel i dimensionerne af triangulariseringen. Dette anses for ugyldigt, fordi triangulariseringen kan være meget stor. Det ville være rart at finde en algoritme, der virker i den logaritmiske tid af størrelsen af ​​triangulariseringen. Men problemet med at finde en kant med modsatte etiketter er PPA-hård selv for dimension . Det følger heraf, at det er usandsynligt at finde en sådan algoritme [6] .

Tilsvarende resultater

Der er flere fikspunktssætninger, der kommer i tre ækvivalente versioner: den algebraiske topologivariant , den kombinatoriske variant og den mængdedækkende variant. Hver mulighed kan bevises separat ved hjælp af helt forskellige argumenter, men hver mulighed kan reduceres til en anden mulighed på samme linje. Derudover kan hvert resultat i den øverste række udledes af resultatet i rækken nedenfor i samme kolonne [7] .

Aglebraisk topologi Kombinatorik Dæksæt
Brouwers fikspunktssætning Sperners Lemma Lemma af Knaster-Kuratovsky-Mazurkiewicz
Borsuk-Ulam teorem Tuckers Lemma Lyusternik-Shnirelman-sætning

Se også

Noter

  1. ↑ Matousek, 2003 , s. 34-45.
  2. ↑ Tucker, 1946 , s. 285-309.
  3. ↑ Freund, Todd, 1981 , s. 321-325.
  4. ↑ Freund, Todd, 1980 .
  5. ↑ Meunier, 2010 , s. 46-64.
  6. ↑ Aisenberg, Bonet, Buss, 2015 .
  7. ↑ Kathryn L. Nyman, Francis Edward Su. En Borsuk–Ulam-ækvivalent, der direkte implicerer Sperners lemma // American Mathematical Monthly . - 2013. - T. 120 , no. 4 . — S. 346–354 . - doi : 10.4169/amer.math.monthly.120.04.346 .

Litteratur