Lema de Sperner

Per a la teorema en la teoria de conjunts extrems vore teorema de Sperner.

El cas bidimensional del lema de Sperner: una coloració de Sperner, en els seus tres triànguls en els vèrtiços de tres colors distints sombreados

En matemàtiques, el lema de Sperner és un resultat combinatori sobre el coloreado de triangulacions, anàloga al teorema del punt fix de Brouwer, que és equivalent.^[1] Establix que cada coloració de Sperner (descrita més alvance) d'una triangulació formada per símplices $n$ -dimensionals conté una cela els vèrtiços de la qual tenen colors diferents.

El resultat inicial d'este tipo va ser demostrat per Emanuel Sperner, en relació en les demostracions d'invarianza del domini. Les coloració de Sperner s'han utilisat per al càlcul efectiu del punt fix i per a la resolució numèrica d'equacions no llineals, i s'apliquen en els algoritmes de divisió justa (de tall de pastiç).

Segons l'Enciclopèdia Matemàtica Soviètica (ed. Iván Vinográdov), una teorema relacionada de 1929 (de Knaster, Borsuk i Mazurkiewicz) també es va conéixer com el lema de Sperner. Este punt s'analisa en la traducció a l'anglés (ed. M. Hazewinkel). Actualment es coneix comunament com lema de Knaster-Kuratowski-Mazurkiewicz.

Enunciat

Cas unidimensional

Archiu:Sperner1d.svg

Eixemple de cas unidimensional

En una dimensió, el lema de Sperner pot considerar-se una versió discreta del teorema del valor intermig. En este cas, bàsicament establix que si una funció discreta pren solament els valors 0 i 1, comença en el valor 0 i termina en el valor 1, deu canviar de valor un número impar de voltes.

Cas bidimensional

El cas bidimensional és el que es menciona en major freqüència. S'enuncia de la següent manera:

Subdividir un triàngul $ABC$ arbitrariamente en una triangulació composta per triànguls més menuts que s'unixen aresta en aresta. Llavors, la coloració de Sperner de la triangulació es definix com l'assignació de tres colors als vèrtiços de la triangulació, de modo que:

Cada u dels tres vèrtiços $A$ , $B$ i $C$ del triàngul inicial té un color distint.
Els vèrtiços que es troben en qualsevol aresta del triàngul $ABC$ tenen solament dos colors: els dos colors en els extrems de l'aresta. Per eixemple, cada vèrtiç de $Plantilla:Overline$ deu tindre el mateix color que $A$ o $C$ .

Llavors, cada coloració de Sperner de cada triangulació té a lo manco un triàngul arcoíris, un triàngul més chicotet en la triangulació els vèrtiços de la qual estan coloreados en els tres colors diferents. Més precisament, deu haver un número impar de triànguls arcoíris.

Cas multidimensional

En el cas general, el lema es referix a un símplex de dimensió $n$ :

𝒜 = A_{1} A_{2} \dots A_{n + 1} .

Considere's qualsevol triangulació $T$ , una divisió disjunta de $𝒜$ en símplices de dimensió $n$ més menuts, que novament es troben cara a cara. Denote's la funció de coloració com:

f : S \to {1, 2, 3, \dots, n, n + 1},

a on $S$ és el conjunt de vèrtiços de $T$ . Una funció de coloració definix una coloració de Sperner quan:

Els vèrtiços del símplex gran es colorean en diferents colors, és dir, sense pèrdua de generalitat, $f (A i)= i$ per a $1 \leq i \leq n + 1$ .
Vèrtiços de $T$ ubicats en qualsevol subcara de dimensió $k$ del símplex gran
$A_{i_{1}} A_{i_{2}} \dots A_{i_{k + 1}}$
estan coloreados solament en els colors

$i_{1}, i_{2}, \dots, i_{k + 1} .$

Llavors, cada coloració de Sperner de cada triangulació del símplex de dimensió $n$ té un número impar d'instàncies d'un símplex arcoíris, és dir, un símplex els vèrtiços del qual estan coloreados en tots els colors de $n + 1$ . En particular, deu haver a lo manco un símplex arcoíris.

Demostracions

Demostració per inducció

Primer s'abordar el cas bidimensional. Considere's un grafo $G$ construït a partir de la triangulació $T$ de la següent manera:

Els vèrtiços de $G$ són els membres de $T$ més l'àrea exterior del triàngul. Dos vèrtiços estan conectats per una aresta si les seues àrees corresponents compartixen una aresta comuna en un extrem de color 1 i l'atre de color 2.

Observe's que en l'interval $AB$ hi ha un número impar d'arestes de color 1-2 (simplement perque A té el color 1 i B el 2; i a mida que s'alvança per $AB$ , deu haver un número impar de canvis de color per a obtindre colors diferents al principi i al final). En els intervals BC i CA, no hi ha arestes de color 1-2. Per lo tant, el vèrtiç de $G$ corresponent a l'àrea exterior té un grau impar. Pero se sap (pel lema de la premuda de mans) que en un grafo finito hi ha un número par de vèrtiços en grau impar. Per lo tant, el grafo restant, excloent l'àrea exterior, té un número impar de vèrtiços en grau impar corresponents als membres de $T$ .

Es pot vore fàcilment que l'únic grau possible d'un triàngul de $T$ és 0, 1 o 2, i que el grau 1 correspon a un triàngul coloreado en els tres colors 1, 2 i 3.

Aixina, s'ha obtingut una conclusió llaugerament més sòlida: en una triangulació $T$ hi ha un número impar (i a lo manco un) de triànguls en tots els colors.

Un cas multidimensional pot demostrar-se per inducció sobre la dimensió d'un símplex. S'aplica el mateix raonament que en el cas bidimensional per a concloure que en una triangulació $n$ -dimensional hi ha un número impar de símplex en tots els colors.

Comentari

Archiu:Spernerlemma.svg

Una triangulació bidimensional simple de la figura d'eixemple, coloreada i nomenada d'acort en els supòsits del lema de Sperner

Archiu:Spernergraph.svg

El grafo derivat de la figura d'eixemple

A continuació, es presenta una explicació de la demostració donada anteriorment, per a els qui no coneixen la teoria de grafos.

Este diagrama numera els colors dels vèrtiços de l'eixemple donat anteriorment. Els triànguls menuts els vèrtiços dels quals tenen números diferents estan sombreados en el gràfic. Cada triàngul chicotet es convertix en un nodo en el nou gràfic derivat de la triangulació. Les lletres minúscules identifiquen les àrees, huit dins de la figura, i l'àrea $i$ designa l'espai exterior.

Com es va descriure anteriorment, els nodos que compartixen una aresta els extrems de la qual estan numerats 1 i 2 s'unixen en el grafo derivat. Per eixemple, el nodo $d$ compartix una aresta en l'àrea exterior $i$ , i els seus vèrtiços tenen números diferents, per lo que també està sombreado. El nodo $b$ no està sombreado perque dos vèrtiços tenen el mateix número, pero està unit a l'àrea exterior.

Es podria afegir un nou triàngul en numeració completa, per eixemple, insertant un nodo numerat 3 en l'aresta entre 1 i 1 del nodo $a$ , i unint eixe nodo a l'atre vèrtiç de $a$ . Per a això, es tindria que crear un parell de nodos nous, com en el cas dels nodos $f$ i $g$ .

Demostració sense inducció

Andrew McLennan i Rabee Tourky varen presentar una demostració diferent, utilisant el nodo símplex. Es realisa en un sol pas, sense inducció.^[2]^[3]

Referències

↑ Flegg, H. Graham (1974). From Geometry to Topology, London: English University Press, pp. 84–89. ISBN 0-340-05324-0.
↑ Anatoly. «Sperner's lemma». Consultat el 20 de juliol de 2024.
↑ “Using Volume to Prove Sperner's Lemma” . Economic Theory 35 (3): 593–597. doi:10.1007/s00199-007-0257-0. ISSN 0938-2259.

Referències

Este artícul conté una traducció derivada de «Lema de Sperner» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Flegg, H. Graham (1974). From Geometry to Topology, London: English University Press, pp. 84–89. ISBN 0-340-05324-0.

[2] Anatoly. «Sperner's lemma». Consultat el 20 de juliol de 2024.

[3] “Using Volume to Prove Sperner's Lemma” . Economic Theory 35 (3): 593–597. doi:10.1007/s00199-007-0257-0. ISSN 0938-2259.

[1]

[2]

[3]