Lemme de Sperner

En mathématiques, le lemme de Sperner, dû à Emanuel Sperner, est un analogue combinatoire du théorème du point fixe de Brouwer. Le lemme de Sperner affirme que chaque coloriage de Sperner d'une triangulation d'un simplexe de dimension n contient une cellule colorée de toutes les n + 1 couleurs. Le premier résultat de ce type fut démontré par Emanuel Sperner en 1928, en relation avec des preuves du théorème de l'invariance du domaine. Les coloriages de Sperner ont été utilisés pour des déterminations effectives de points fixes, dans des algorithmes de résolution d'équations, et sont employés dans des procédures de partage équitable. En dimension 1, le lemme de Sperner peut être vu comme une version discrète du théorème des valeurs intermédiaires. Il affirme essentiellement qu'une fonction définie en un nombre fini de points, ne prenant que les valeurs 0 et 1, commençant à la valeur 0 et terminant en 1, doit changer de valeur un nombre impair de fois. Sur la figure de droite, ceci est représenté par les deux couleurs, avec 5 changements de couleurs de haut en bas. Le cas de la dimension 2 est celui auquel on se réfère le plus souvent. Il s'énonce ainsi : On se donne un triangle ABC, et une triangulation T de ce triangle. L'ensemble S des sommets de T est coloré avec 3 couleurs, de telle sorte que A, B et C sont colorés respectivement des couleurs 1, 2 et 3. Les sommets situés sur un côté de ABC sont coloriés avec l'une des deux couleurs des extrémités de ce côté. Par exemple, chaque sommet sur AC doit recevoir la couleur 1 ou 3. Il existe alors un triangle de T, dont les sommets sont colorés avec les trois couleurs. Plus précisément, il y a un nombre impair de tels triangles. Dans le cas général, le lemme concerne un simplexe de dimension n Soit T une triangulation, c'est-à-dire une partition de en simplexes de dimension n, plus petits et disjoints.