Tuckers Lemma

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 februari 2021; verifiering kräver 1 redigering .

Tuckers lemma  är en kombinatorisk analog till Borsuk-Ulam-satsen , uppkallad efter Albert W. Tucker .

Kärnan i lemmat är följande:

Låt T vara en triangulering av en sluten n -dimensionell kula . Antag att T är antipodalsymmetriskt vid sfärens gräns . Detta betyder att delmängden av trianguleringssimpliciteter som ligger på bildar en triangulering av sfären , och om simplexen σ tillhör denna triangulering, så hör -σ också till den (för figuren till höger är simplicerna på cirkeln bågar , så villkoret som beskrivs ovan betyder att för varje båge har en båge symmetrisk kring cirkelns centrum).

Låta vara märkningen av hörn av trianguleringen T som uppfyller paritetsvillkoret på , Det vill säga för någon vertex . Sedan säger Tuckers lemma att trianguleringen T innehåller en kant med motsatta etiketter , det vill säga en kant (1-simplex) vars hörn är märkta med samma nummer men med olika tecken [1] .

Bevis

Det första beviset var icke-konstruktivt (bevis genom motsägelse) [2] .

Senare hittades ett konstruktivt bevis, som ges av en algoritm som hittar en kant med motsatta etiketter [3] [4] . I grund och botten är algoritmer sökvägsbaserade - de börjar vid någon punkt eller kanten av trianguleringen och fortsätter från simplex till simplex enligt föreskrivna regler medan processen fortfarande pågår. Det kan bevisas att banan måste sluta på en simplex som innehåller en kant med motsatta etiketter.

Ett enkelt bevis på Tuckers lemma använder det mer allmänna Ki Fans lemma , som har ett enkelt algoritmiskt bevis.

Följande beskrivning illustrerar algoritmen för [5] . Observera att det i det här fallet är en disk med 4 möjliga etiketter: , som i figuren ovan.

Låt oss börja utanför bollen och titta på etiketterna på gränsen. Eftersom etiketten är en udda funktion på gränsen, måste gränsen innehålla positiva och negativa etiketter:

Låt oss välja en kant och gå igenom den. Det kan finnas tre fall:

Vi kan hamna utanför cirkeln som ett resultat. Men eftersom antalet kanter på gränsen är udda måste det finnas en ny tidigare obesökt kant på gränsen. Vi går igenom det och fortsätter processen.

Resan måste sluta inuti cirkeln antingen i simplex a eller i simplex . Q.E.D.

Öppettider

Körtiden för den beskrivna algoritmen är polynom i dimensionerna för triangulariseringen. Detta anses ogiltigt eftersom triangulariseringen kan vara mycket stor. Det skulle vara trevligt att hitta en algoritm som fungerar i den logaritmiska tiden för storleken på triangulariseringen. Men problemet med att hitta en kant med motsatta etiketter är PPA-hårt även för dimension . Det följer att det är osannolikt att hitta en sådan algoritm [6] .

Motsvarande resultat

Det finns flera fixpunktssatser som finns i tre ekvivalenta versioner: den algebraiska topologivarianten , den kombinatoriska varianten och den mängdtäckande varianten. Varje alternativ kan bevisas separat med hjälp av helt olika argument, men varje alternativ kan reduceras till ett annat alternativ på samma rad. Dessutom kan varje resultat i den översta raden härledas från resultatet i raden nedan i samma kolumn [7] .

Aglebraisk topologi Kombinatorik Täckningsset
Brouwers fixpunktssats Sperners Lemma Lemma från Knaster-Kuratovsky-Mazurkiewicz
Borsuk-Ulams teorem Tuckers Lemma Lyusternik-Shnirelman teorem

Se även

Anteckningar

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

Litteratur