Sperner-lemma
A Sperner-lemma Emanuel Spernertől származik, aki 1927-ben, doktori disszertációjában ezt az állítást több fontos tétel bizonyításához használta segítségül.
Kétdimenziós eset szerkesztés
Adott egy ABC háromszög. Ennek egy háromszögelésén a következőt értjük: felveszünk véges sok pontot a háromszög belsejében és az élein, majd ezek közül néhányat összekötünk egyenes szakaszokkal úgy, hogy a szakaszok ne metsszék egymást, és a keletkező tartományok háromszögek legyenek. (A háromszögelést tekinthetjük egy gráfnak is, nevezzük ezt T-nek.) T csúcsait színezzük ki úgy, hogy
- az A csúcs kapja az 1-es színt,
- a B csúcs kapja a 2-es színt,
- a C csúcs pedig a 3-as színt,
- Az AB élen csak 1 és 2 színű csúcsok vannak (most megengedhető, hogy szomszédos csúcsok egyező színűek legyenek), az AC élen csak 1 és 3, a BC élen pedig csak 2 és 3 színű csúcsok szerepelnek.
A lemma állítása szerint ekkor van olyan kis háromszög, melynek csúcsai mind különböző színűek.
Bizonyítás szerkesztés
Tekintsük a következő G gráfot:
- G csúcsainak feleltessük meg T síkgráf egy-egy tartományát,
- és G csúcsai között pontosan akkor fusson él, ha a nekik megfelelő tartományoknak T-ben olyan közös határuk volt, melynek egyik végpontja 1-es, a másik pedig 2-es színnel volt színezve.
Észrevehetjük, hogy az eredeti háromszög AB élén páratlan sok ilyen 1-2 végpontú határoló éldarab lesz, hiszen A színe 1, B színe 2, és AB-n végighaladva páratlan sokszor válthatunk színt úgy, hogy a két végpontban (A-ban és B-ben) különböző színt kapjunk. Így az a csúcs G-ben, melyet T külső tartományának feleltettünk meg, láthatóan páratlan fokszámú lesz. (A BC és az AC éleket nem vizsgáljuk, hiszen ott eleve nem lehet 1-2 színű él). Ugyanakkor azt is tudjuk, hogy bármely gráf fokszámainak összege páros. Így kell legyen még legalább egy olyan pont G-ben, melynek fokszáma páratlan. Azaz van olyan tartomány (háromszög) T-ben, melynek páratlan sok 1-2 éle van. Három ilyen éle értelemszerűen nem lehet. Ha pontosan egy darab 1-2-es éle van, az azt jelenti, hogy a kis háromszög harmadik csúcsa szükségszerűen 3-as színű, így tehát létezik olyan tartomány, melynek mindhárom csúcsa különböző színű.
n dimenziós eset szerkesztés
A fenti állítást általánosíthatjuk kettőről tetszőlegesen sok dimenzióra is. Tekintsük adottnak A n dimenziós szimplexet, melynek csúcsai:
A1, A2,…, Ai, …, An
és ennek egy „háromszögelését”, ami ebben az esetben azt jelenti, hogy A-t kisebb, különálló n dimenziós szimplexekre osztjuk.
A színezés az előző esethez hasonlóan történjen,
- rendelkezésre állnak az {1, 2,…, i,.., n+1} színek,
- A csúcsai mind különbözőek legyenek,
- Ai színe legyen i minden i-re,
- azok a csúcsok, melyek egy Ai(1), Ai(2)…Ai(k) által meghatározott k dimenziós hipersíkon helyezkednek el, legyenek i(1), i(2), …i(k) színek valamelyikével színezve.
A lemma állítása szerint ekkor létezik olyan n dimenziós szimplex A belsejében, melynek csúcsainak színezéséhez mind az n+1 színt felhasználtuk.
Bizonyítása szerkesztés
Dimenziókra történő teljes indukcióval történik. A kétdimenziós esethez hasonló érveléssel belátható, hogy létezik páratlan sok olyan szimplex A-ban, melynek színezéséhez a teljes színkészletet felhasználtuk.
