Sperners Lemma

Sperners lemma är en kombinatorisk analog till Brouwers fixpunktssats , ett av de viktigaste resultaten av kombinatorisk topologi. Påstår att för varje Sperner vertexfärgning i en triangulering av en n - dimensionell simplex finns det en trianguleringscell vars hörn är färgade i alla färger. Det första resultatet av denna bevisades av Sperner

Endimensionellt fall

I det endimensionella fallet kan Sperners lemma ses som en diskret analog till Bolzano-Cauchy-satsen . Hon säger att om ett stort segment är uppdelat i undersegment och 1:or och 2:or placeras vid segmentens hörn, så, förutsatt att det finns olika värden vid hörn av det stora segmentet, finns det ett segment av underavdelning, vid vars hörn det finns olika värden.

Tvådimensionellt fall

Det här alternativet är det vanligaste. Den är formulerad enligt följande:

Givet en triangel vars hörn är märkta 0, 1 och 2, och dess triangulering. Trianguleringspunkten var märkta med samma värden så att varje vertex på sidan av den ursprungliga triangeln skulle märkas med en av vertexetiketterna på den sidan. Då finns det nödvändigtvis en partitionstriangel märkt 0, 1, 2.

Flerdimensionellt fall

Generellt gäller lemmat trianguleringen av ett n -dimensionellt simplex

{\mathcal {A}}=A_{1}A_{2}\ldots A_{{n+1}}.

Betrakta dess triangulering T , som är en uppdelning i mindre n -dimensionella förenklingar. Beteckna vertexfärgfunktionen som , där S betecknar uppsättningen av hörn för trianguleringen T . En färgning kallas Sperner-färgning om följande regler är uppfyllda: $\mathcal{A}$ ${\displaystyle f\colon S\rightarrow \left\{1,2,3,\dots ,n,n+1\right\))$

Topparna av den stora simplexen färgas olika, det vill säga: f ( A i ) = i för 1 ≤ i ≤ n +1.
De hörn T som ligger i en k -dimensionell yta av den stora simplexen

A_{{i_{1}}}A_{{i_{2}}}\ldots A_{{i_{k}}}

målad i färgerna på de hörn som bildar den

f(A_{{i_{1}}}),f(A_{{i_{2}}}),\ldots ,f(A_{{i_{k}}}).

Om färgen visar sig vara Sperner, så finns det en trianguleringssimplex T vars hörn är färgade med alla färger.

Bevis

Även om det endimensionella fallet är uppenbart, kommer vi att bevisa det tvådimensionella fallet genom att först generalisera påståendet. Beviset för det flerdimensionella fallet erhålls på liknande sätt genom induktion.

Betrakta en graf G konstruerad från en triangulering T enligt följande:

Topparna av G kommer att vara trianglarna T och området utanför den stora triangeln. Vi förbinder två hörn med en kant om regionerna som motsvarar dem har ett gemensamt segment, vars hörn är färgade 1 och 2. På sidan som förbinder de två hörnen i en stor triangel, färgade 1 och 2, finns det ett udda nummer av segment med hörn 1 och 2, vilket betyder , som motsvarar det yttre området är udda. Eftersom grafen måste ha ett jämnt antal hörn av udda grad, finns det ett udda antal (och därmed minst en) hörn av udda grad som motsvarar trianglarna T .

Det är lätt att kontrollera att de möjliga graderna av hörn som motsvarar trianglar är 0, 1 eller 2, och 1 motsvarar en triangel vars hörn är färgade i alla tre färgerna.

I det flerdimensionella fallet måste man på exakt samma sätt bevisa förekomsten av ett udda antal partitionssimpliceringar vars hörn är färgade i alla färger.

Applikationer

På basis av Sperner-lemmat konstrueras ett av bevisen för Brouwers fixpunktssats .
Sats om att skära en kvadrat i trianglar med lika stor yta

Litteratur

Shashkin Yu. A. Fasta punkter. - Moskva: Nauka, 1989. - 80 sid. — (Populära föreläsningar om matematik). — ISBN 5-02-013922-X .

Se även

Länkar

Proof of the lemma (engelska) , Cut-the-knoten .
E. Epifanov, Pirate's share , Elementy.ru , 2014. (ett exempel på tillämpningen av Sperners lemma)
ELLER Musin Sperners Lemma: Tillämpningar och generaliseringar. Sommarskola "Modern Mathematics", 2015, Dubna.