14:00
17:00

Cette thèse porte sur la reconfiguration combinatoire et des problèmes structurels ou géométriques. Nous associons à un espace de configuration et à une opération élémentaire un graphe de reconfiguration, dont les sommets sont les configurations et dans lequel deux configurations sont adjacentes si elles diffèrent par une opération. La reconfiguration est motivée par l’échantillonnage aléatoire et des applications en mécanique statistique.
Cela soulève des questions algorithmiques, probabilistes et structurelles, notamment sur la complexité du problème d’accessibilité et la géométrie du graphe de reconfiguration.
La principale opération de reconfiguration étudiée ici est appelée changement de Kempe et opère sur les colorations propres d’un graphe. Nous étudions ensuite d’autres opérations de reconfiguration motivées par la topologie en basse dimension. Nous présentons plusieurs bornes polynomiales sur le diamètre du graphe de reconfiguration et obtenons divers résultats algorithmiques.

English
Amphi LaBRI