Spernerin Lemma

Spernerin lemma on kombinatorinen analogi Brouwerin kiinteän pisteen lauseelle , joka on yksi kombinatorisen topologian tärkeimmistä tuloksista. Väittää , että jokaiselle Sperner- pisteen värjäykselle n - ulotteisen simpleksin kolmiossa on kolmiomittaussolu , jonka kärjet on värjätty kaikissa väreissä. Ensimmäisen tämän tuloksen todisti Sperner

Yksiulotteinen kotelo

Yksiulotteisessa tapauksessa Spernerin lemmaa voidaan pitää Bolzano–Cauchy-lauseen diskreettianalogina . Hän toteaa, että jos suuri segmentti jaetaan osasegmenteiksi ja segmenttien kärkipisteisiin sijoitetaan 1s ja 2s, niin jos suuren segmentin kärjeissä on erilaisia arvoja, on segmentin segmentti. alajako, jonka kärjessä on erilaisia arvoja.

Kaksiulotteinen tapaus

Tämä vaihtoehto on yleisin. Se on muotoiltu seuraavasti:

Annettu kolmio, jonka kärjet on merkitty 0, 1 ja 2, ja sen kolmio. Kolmiomittauspisteet merkittiin samoilla arvoilla, jotta mikä tahansa alkuperäisen kolmion puolella oleva kärki olisi merkitty jollakin sen puolen kärkimerkinnöistä. Silloin on välttämättä olemassa osiokolmio, jonka nimi on 0, 1, 2.

Moniulotteinen tapaus

Yleisesti ottaen lemma koskee n - ulotteisen simpleksin kolmiota

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

Tarkastellaan sen kolmiota T , joka on osio pienempiin n -ulotteisiin yksinkertaisteisiin. Merkitään kärjen värifunktiota , missä S tarkoittaa kolmion T kärkijoukkoa . Väritystä kutsutaan Sperner-värjäyksellä, jos seuraavat säännöt täyttyvät: $\mathcal{A}$ ${\displaystyle f\colon S\rightarrow \left\{1,2,3,\dots ,n,n+1\right\))$

Suuren simpleksin kärjet ovat erivärisiä, eli: f ( A i ) = i , kun 1 ≤ i ≤ n +1.
Ne kärjet T , jotka sijaitsevat suuren simpleksin k -ulotteisessa pinnassa

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

maalattu sen muodostavien kärkien väreillä

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

Jos väritys osoittautuu Sperneriksi, on olemassa kolmiomittaus simpleksi T , jonka kärjet on värjätty kaikilla väreillä.

Todiste

Vaikka yksiulotteinen tapaus on ilmeinen, todistamme kaksiulotteisen tapauksen ensin yleistämällä väitteen. Moniulotteisen tapauksen todistus saadaan samalla tavalla induktiolla.

Tarkastellaan kolmiosta T muodostettua kuvaajaa G seuraavasti:

G : n kärjet ovat kolmiot T ja suuren kolmion ulkopuolella oleva alue. Yhdistämme kaksi kärkeä reunalla, jos niitä vastaavilla alueilla on yhteinen segmentti, jonka kärjet ovat värjätty 1 ja 2. Suuren kolmion, värjätty 1 ja 2, kaksi kärkeä yhdistävällä puolella on pariton luku segmenttien kärjet 1 ja 2, mikä tarkoittaa , Vastaa ulompaa aluetta on pariton. Koska graafissa täytyy olla parillinen määrä parittoman asteen pisteitä, on kolmioita T vastaava pariton määrä (ja siten ainakin yksi) parittoman asteen pisteitä .

On helppo tarkistaa, että kolmioita vastaavien pisteiden mahdolliset asteet ovat 0, 1 tai 2 ja 1 vastaa kolmiota, jonka kärjet on väritetty kaikilla kolmella värillä.

Moniulotteisessa tapauksessa täytyy todistaa täsmälleen samalla tavalla, että on olemassa pariton määrä osion yksinkertaistuksia, joiden kärjet on väritetty kaikilla väreillä.

Sovellukset

Sperner-lemman perusteella rakennetaan yksi Brouwerin kiinteän pisteen lauseen todisteista.
Lause neliön leikkaamisesta samankokoisiksi kolmioksi

Kirjallisuus

Shashkin Yu. A. Kiinteät pisteet. - Moskova: Nauka, 1989. - 80 s. — (Suosittuja matematiikan luentoja). — ISBN 5-02-013922-X .

Katso myös

Linkit

Lemman todiste (englanniksi) , leikkaa solmu .
E. Epifanov, Pirate's share , Elementy.ru , 2014. (esimerkki Spernerin lemman soveltamisesta)
TAI Musin Spernerin Lemma: Sovellukset ja yleistykset. Kesäkoulu "Moderni matematiikka", 2015, Dubna.