Deux applications du Théorème de Borsuk-Ulam à la combinatoire.

En 1979, pour la première fois dans l'histoire de la combinatoire, un théorème de topologie algébrique était appliqué à un problème purement combinatoire. En effet, en utilisant le théorème de Borsuk-Ulam, Lovasz résolvait une conjecture que Kneser avait faite en 1955 et qui, dans le formalisme de la théorie des graphes, s'énonce:
Soit deux entiers k et n tel que n>2k-1. On considère le graphe G dont les sommets sont les parties à k éléments de {1,2,...,n} et dont les arêtes relient les parties disjointes. Alors le nombre chromatique de G est n-2k+2 (une coloration d'un graphe, c'est une affectation de couleurs aux sommets telle que les extrémités de toute arête soit de couleurs différentes; le nombre chromatique, c'est le nombre minimum de couleurs permettant de colorier le graphe).
Depuis, beaucoup d'autres applications à la combinatoire du théorème de Borsuk ont été trouvées. Après avoir expliqué une preuve récente de la conjecture de Kneser, qui utilise toujours le théorème de Borsuk, nous présenterons une de ces applications, due à Noga Alon en 1986: si 2 voleurs volent un collier de n perles, les perles pouvant être de t types différents, et qu'ils veulent se le partager équitablement, ils peuvent toujours le faire en au plus t coupes.