2013

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Programmation linéaire colorée
Description:	Pauline Sarrabezolles Considérons d + 1 ensembles de points de R^d en position générique, et attribuons à chacun des ces ensembles une couleur distincte. D'après le théorème de Carathéodory coloré, prouvé par Imre Barany en 1982, si un point est contenu dans l'enveloppe convexe de chacun de ces ensembles, alors il est contenu dans l'enveloppe convexe d'un simplexe formé d'un point de chaque couleur. Un tel simplexe est dit arc-en-ciel. La conjecture de la profondeur simpliciale colorée, formulée par Antoine Deza et ses coauteurs en 2006, dit qu'un tel point est en fait contenu dans au moins d^2 + 1 simplexes arc-en-ciel, ce qui a été vérifié par différents auteurs pour d = 1, 2 et 3. Nous vérifions cette conjecture en dimension 4 et améliorons les bornes connues dans les dimensions plus élevées. Ces résultats sont obtenus grâce à une généralisation combinatoire des configurations colorées de points, suggérée par Imre Barany : les systèmes octaédriques. Nous présentons de plus des algorithmes résolvant divers problèmes de programmation linéaire colorée.