Sperner Lemmája

A Sperner-lemm Brouwer fixpont-tételének kombinatorikus analógja , amely a kombinatorikus topológia egyik fő eredménye. Azt állítja, hogy bármely Sperner -csúcs színezéséhez egy n - dimenziós szimplex háromszögelésében van egy háromszögelési cella, amelynek csúcsai minden színben ki vannak festve. Az első ilyen Sperner bizonyította

Egydimenziós tok

Az egydimenziós esetben a Sperner-lemmát a Bolzano–Cauchy-tétel diszkrét analógjaként tekinthetjük . Azt állítja, hogy ha egy nagy szegmenst alszegmensekre osztunk, és a szegmensek csúcsaiban 1-eket és 2-ket helyezünk, akkor, feltéve, hogy a nagy szegmens csúcsaiban különböző értékek vannak, van egy szegmens a szegmensből. felosztás, amelynek csúcsaiban különböző értékek találhatók.

Kétdimenziós eset

Ez a lehetőség a leggyakoribb. A következőképpen van megfogalmazva:

Adott egy háromszög, amelynek csúcsai 0, 1 és 2, és annak háromszögelése. A háromszögelési csúcsokat ugyanazokkal az értékekkel jelölték meg, így az eredeti háromszög oldalán lévő bármely csúcsot az azon az oldalon lévő csúcscímkék egyikével jelölték meg. Ekkor szükségszerűen létezik egy 0, 1, 2 címkével ellátott partíciós háromszög.

Többdimenziós eset

Általában a lemma egy n - dimenziós szimplex háromszögelésére vonatkozik

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

Tekintsük a T háromszögletét, amely kisebb n - dimenziós egyszerűségekre való felosztás . Jelölje a csúcsszínfüggvényt így , ahol S a T háromszögelés csúcsainak halmazát jelöli . Egy színezést Sperner-színezésnek nevezünk, ha a következő szabályok teljesülnek: $\mathcal{A}$ ${\displaystyle f\colon S\rightarrow \left\{1,2,3,\dots ,n,n+1\right\))$

A nagy szimplex csúcsai különböző színűek, azaz: f ( A i ) = i 1 ≤ i ≤ n +1 esetén.
Azok a T csúcsok, amelyek a nagy szimplex egy k -dimenziós lapjában helyezkednek el

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

az azt alkotó csúcsok színeire festve

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

Ha kiderül, hogy a színezés Sperner, akkor létezik egy T szimplex háromszögelés, amelynek csúcsai minden színnel ki vannak színezve.

Bizonyítás

Míg az egydimenziós eset nyilvánvaló, a kétdimenziós esetet először az állítás általánosításával fogjuk bizonyítani. A többdimenziós eset bizonyítását hasonló módon indukcióval kapjuk meg.

Tekintsünk egy G gráfot egy T háromszögelésből a következőképpen:

G csúcsai a T háromszögek és a nagy háromszögön kívüli terület lesznek . Két csúcsot összekötünk éllel, ha a hozzájuk tartozó régióknak van egy közös szakasza, melynek csúcsai 1-es és 2-es színűek. Egy nagy, 1-es és 2-es színű háromszög két csúcsát összekötő oldalon páratlan szám található. 1. és 2. csúcsú szegmensek, ami azt jelenti , hogy a külső régiónak megfelelő páratlan. Mivel a gráfnak páros számú páratlan fokú csúcsot kell tartalmaznia, a T háromszögeknek van páratlan számú (és így legalább egy) páratlan fokú csúcsa .

Könnyen ellenőrizhető, hogy a háromszögeknek megfelelő csúcsok lehetséges fokai 0, 1 vagy 2, és 1 olyan háromszögnek felel meg, amelynek csúcsai mindhárom színben vannak színezve.

A többdimenziós esetben pontosan ugyanígy kell bizonyítani páratlan számú partíciós egyszerűség létezését, amelyek csúcsai minden színben ki vannak festve.

Alkalmazások

A Sperner-lemma alapján megszerkesztjük a Brouwer-féle fixpont tétel egyik bizonyítását.
Tétel egy négyzet egyenlő területű háromszögekre vágásáról

Irodalom

Shashkin Yu. A. Rögzített pontok. - Moszkva: Nauka, 1989. - 80 p. — (Népszerű matematikai előadások). — ISBN 5-02-013922-X .

Lásd még

Linkek

A lemma bizonyítása (angolul) , Cut-the-knot .
E. Epifanov, Pirate's share , Elementy.ru , 2014. (Példa a Sperner-lemma alkalmazására)
VAGY Musin Sperner Lemmája: Alkalmazások és általánosítások. Nyári iskola "Modern Matematika", 2015, Dubna.