Sperner-lemma

A Wikipédiából, a szabad enciklopédiából

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 | forrásszöveg szerkesztése]

A kétdimenziós eset

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]