|
|
 |
|
Mardi 22 Octobre
| 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. |
|
|
