Sperners Lemma

Sperners lemma er en kombinatorisk analog til Brouwers fikspunktssætning , et af hovedresultaterne af kombinatorisk topologi. Hævder, at for enhver Sperner - vertexfarvning i en triangulering af en n - dimensional simplex , er der en trianguleringscelle, hvis hjørner er farvet i alle farver. Det første resultat af denne blev bevist af Sperner

Endimensionel kasus

I det endimensionelle tilfælde kan Sperners lemma ses som en diskret analog til Bolzano-Cauchy-sætningen . Hun anfører, at hvis et stort segment er opdelt i undersegmenter, og 1'ere og 2'ere placeres ved segmenternes spidser, så er der, forudsat at der er forskellige værdier ved spidserne af det store segment, et segment af underafdeling, i hvis toppunkter der er forskellige værdier.

Todimensional kasus

Denne mulighed er den mest almindelige. Den er formuleret som følger:

Givet en trekant, hvis toppunkter er mærket 0, 1 og 2, og dens trekant. Trianguleringshjørnerne blev mærket med de samme værdier, så ethvert knudepunkt på siden af den oprindelige trekant ville blive mærket med en af knudepunkterne på den side. Så eksisterer der nødvendigvis en partitionstrekant mærket 0, 1, 2.

Multidimensional sag

Generelt omhandler lemmaet trianguleringen af et n -dimensionelt simpleks

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

Overvej dens triangulering T , som er en opdeling i mindre n -dimensionelle simplicer. Betegn toppunktets farvefunktion som , hvor S angiver mængden af toppunkter for trianguleringen T . En farvning kaldes en Sperner-farvning, hvis følgende regler er opfyldt: $\mathcal{A}$ ${\displaystyle f\colon S\rightarrow \left\{1,2,3,\dots ,n,n+1\right\))$

Hjørnerne i det store simpleks er farvet forskelligt, det vil sige: f ( A i ) = i for 1 ≤ i ≤ n +1.
De hjørner T , der ligger i en k -dimensionel flade af den store simplex

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

malet i farverne på de hjørner, der danner det

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

Hvis farven viser sig at være Sperner, så eksisterer der en triangulation simplex T , hvis hjørner er farvet med alle farver.

Bevis

Mens det endimensionelle tilfælde er indlysende, vil vi bevise det todimensionelle tilfælde ved først at generalisere påstanden. Beviset for det flerdimensionale tilfælde opnås på lignende måde ved induktion.

Overvej en graf G konstrueret ud fra en triangulering T som følger:

Hjørnerne på G vil være trekanter T og området uden for den store trekant. Vi forbinder to hjørner med en kant, hvis regionerne, der svarer til dem, har et fælles segment, hvis hjørner er farvet 1 og 2. På den side, der forbinder de to knudepunkter i en stor trekant, farvet 1 og 2, er der et ulige tal af segmenter med toppunkter 1 og 2, hvilket betyder , svarende til det ydre område er ulige. Da grafen skal have et lige antal hjørner af ulige grad, er der et ulige antal (og dermed mindst et) hjørner af ulige grad svarende til trekanter T .

Det er let at kontrollere, at de mulige grader af hjørner svarende til trekanter er 0, 1 eller 2, og 1 svarer til en trekant, hvis hjørner er farvet i alle tre farver.

I det flerdimensionale tilfælde skal man på nøjagtig samme måde bevise eksistensen af et ulige antal partitionssimpliceringer, hvis hjørner er farvet i alle farver.

Ansøgninger

På basis af Sperner-lemmaet er et af beviserne for Brouwers fikspunktssætning konstrueret
Sætning om at skære et kvadrat i trekanter med samme areal

Litteratur

Shashkin Yu. A. Faste punkter. - Moskva: Nauka, 1989. - 80 s. — (Populære forelæsninger om matematik). — ISBN 5-02-013922-X .