matematikai állítás From Wikipedia, the free encyclopedia
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.
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
A lemma állítása szerint ekkor van olyan kis háromszög, melynek csúcsai mind különböző színűek.
Tekintsük a következő G gráfot:
É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ű.
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,
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.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.