Lemme de Sperner
Bonjour,
1. très content d'inaugurer la nouvelle rubrique!
2. quelqu'un peut-il prendre 2 minutes pour me faire comprendre le lemme de Sperner? Wikipédia n'aide pas beaucoup et je n'ai aucun spécialiste dans mes relations immédiates...
Amicalement,
F.D.
1. très content d'inaugurer la nouvelle rubrique!
2. quelqu'un peut-il prendre 2 minutes pour me faire comprendre le lemme de Sperner? Wikipédia n'aide pas beaucoup et je n'ai aucun spécialiste dans mes relations immédiates...
Amicalement,
F.D.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je te conseille le ivre "proofs from the book" (ou raisonnements divins" en français) où ce lemme est bien expliqué je trouve ainsi que pourquoi Sperner=>Brouwer. Ca ne traite que la dim 2 par contre, mais une fois cette demo maîtrisée tu ne devrais pas avoir trop de mal à la généraliser en dim supérieure, ou du moins à comprendre plus facilement les preuves plus abstraites trouvables ailleurs.
ps: ça m'a fait bizarre d'arriver sur l'index et de voir un "discussions:2 messages:3"..J'ai cru à un bug au début
toutefois j'ai déjà lu "proofs from the book" et j'avoue ne toujours pas comprendre grand-chose au lemme de Sperner, or, c'est l'ingrédient magique du théorème de Mémère Pépère...
Si quelqu'un peut prendre 5 minutes pour m'expliquer... merci!
F.D.
j'ai le livre " Raisonnements divins". Si tu peux préciser le(s) passage(s) qui te pose(nt) problème dans la démo de Sperner, je vais essayer de t'aider.
Amicalement
Paul
si $f$ est une quelconque application de $J$ dans $J$ où $J:=[0;1]^n$ alors il existe des convexes de diamètres arbitrairement petits $C$ qui sont tels que l'enveloppe convexe de l'image de $C$ par $f$ contient $C$.
En particulier, si $f$ est continue, ça impliquera l'existence d'un point fixe pour $f$
(sans garantie, j'exprime une image de marque des "sperneries" qui contituent une certaine famille de procédés relativement puissants dans cette veine-là)
Très content qu'un sous forum soit dédié à la combinatoire, je mets mon grain de sel et tente de montrer que le fécond lemme de Sperner est très joli. Je le tente en couleurs.
Quitte à être moqué par les spécialistes de la couleur, je la fais à l'ancienne: trois couleurs primaires (bleu, rouge, jaune), trois complémentaires (violet, orange, vert) et le marron, mélange des trois primaires.
Un triangle de Sperner a ses trois sommets peints chacun par une des trois couleurs primaires ( B, R , J). S'en suivent, "naturellement", la couleur et de ses côtés et de son intérieur (identifié à lui-même): ainsi un triangle BBJ a deux sommets bleus et un jaune, un côté bleu et deux verts, et il est vert; pour qu'un triangle soit marron, il faut et il suffit que ses trois sommets soient de couleurs différentes, autrement dit que ses trois côtés le soient aussi.
On part d'un triangle de Sperner, marron, dit Grand Triangle. On le décompose en Petits Triangles (façon puzzle) de Sperner, dont on n'exige qu'une chose: tout sommet d'un Petit Triangle, s'il appartient à un des côtés du Grand, doit avoir la couleur d'une des deux extrémités de ce côté du Grand. (ainsi tout sommet d'un Petit Triangle qui se trouve sur le côté violet du Grand Triangle ne peut être jaune)
Le lemme de Sperner assure que toute triangulation du type ci-dessus comporte un nombre impair (en particulier au moins un) de triangle(s)marron(s).
La suite si on me la demande.
Amicalement
Paul
Quitte à parler de couleurs, ce serait quand même mieux si tu nous montrais un joli dessin avec les dites couleurs.
Cordialement,
Rescassol
Amicalement
Paul
Peut-être ce soir, après mes 7 h de surveillance de bac, ou demain matin.
Cordialement,
Rescassol
devant m'absenter quinze jours, je termine la démo du lemme de Sperner.
La khôlossal astuce est la suivante: Le côté BR ,primitivement violet, du Grand Triangle se retrouve après triangulation partitionné en segments qui ne peuvent être que rouges, bleus ou violets. LE NOMBRE DE CES SEGMENTS QUI SONT VIOLETS EST IMPAIR.
En effet le "mot" qu'on peut lire sur ce côté primitivement violet commence toujours par B et finit toujours par R et ce quelle qu'ait été la partition. Or dans un tel mot (où seules les lettres B et R apparaissent) le nombre d'alternances BR excède de 1 le nombre d'alternances RB, si bien que le nombre total d'alternances est impair. Et il y a bijection entre les alternances et les segments violets.
Le Grand Triangle a été partitionné en N Petits Triangles. Donc le plan en N+1 régions. La frontière de chacune des N régions triangulaires est formée par ses trois côtés et celle du complémentaire du Grand Triangle (on dira désormais "la Mer") par la réunion des côtés des Petits Triangles qui partitionnent les côtés du Grand triangle.
Désormais on ne s'intéresse plus qu'aux régions qui ont du violet dans leur frontière: on les dira "distinguées" et on dira que deux d'entre elles sont voisines si elles sont distinctes et si leurs frontières ont en commun un segment violet.
La Mer est une région distinguée qui a un nombre impair de voisines (conséquence de la kholossal astuce ET du fait qu'il n'y a pas de violet sur les deux autres côtés du Grand Triangle).
Les régions distinguées et triangulaires ont une ou deux voisines (dont éventuellement la Mer) selon qu'elles ont exactement un ou exactement deux côtés violets (trois côtés violets, c'est impossible!).
Deux quelconques régions voisines sont reliées par un unique pont. Appelons paire (resp. impaire) une région d'où part un nombre pair (resp. impair) de ponts. Un pont ayant deux extrémités, le nombre de régions impaires est nécessairement pair! (grand classique). Or la Mer est une région impaire. Il y a donc un nombre impair de régions impaires autres que la Mer: ce sont les régions triangulaires distinguées d'où ne part qu'un pont, i.e celles qui ont exactement un côté violet: ce sont exactement les régions marron.
Bon, avec le vocabulaire de la théorie des graphes, ça aurait sûrement été plus clair mais le dessin de Rescassol (condoléances pour ta journée de surveillance) va colorer tout ça!
Amicalement
Paul
Si je ne me suis pas trompé, voilà qui devrait correspondre au dessin dans la marge de la page 162 de "Raisonnements divins":
Paul
"le bord supérieur de l'aile droite du papillon marron situé dans le sud-ouest du dessin de Rescassol est violet et non marron".
ou "comment empapaouter les lépidoptères"
C'est corrigé.
Et voilà le fichier Géogébra: