Lemme de Sperner

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 Il existe alors un triangle de T, dont les sommets sont colorés avec les trois couleurs.