Full labellings and balanced configurations : topological aspects of Combinatorial Optimization
Pleins étiquetages et configurations équilibrées : aspects topologiques de l'Optimisation Combinatoire
Résumé
The main goal of this thesis is to develop combinatorial and constructive versions of some theorems in combinatorial optimization necessitating tools from algebraic topology. Generalizations of Sperner's lemma and Ky Fan's combinatorial formulae are proposed, as well as applications to the colorings of Kneser graphs and to the famous splitting necklace theorem. A scheduling problem, which has some common aspects with this last theorem, is treated as well. Finally, the last chapter contains new results concerning sigma-games (lights out games) on the grid.
Cette thèse traite principalement des contreparties combinatoires et constructives de certains théorèmes d'optimisation combinatoire qui font appel à des outils de topologie algébrique. Des généralisations des lemmes de Sperner et des formules combinatoires de Ky Fan sont proposées, ainsi que des applications à la coloration des graphes de Kneser et au célèbre problème du partage équitable du collier. Un problème d'ordonnancement lié à ce dernier problème est également abordé. Enfin, le dernier chapitre contient des résultats nouveaux pour les sigma-jeux (jeux de lampes) sur la grille.
Loading...