/Soutenance de thèse/
/Présentation en anglais/P resentation in english/

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.

Jury :

* Marie Albenque: Directrice de recherche CNRS: Université Paris Cité - Examinatrice
* Marthe Bonamy: Chargée de recherche CNRS: Université de Bordeaux - Directrice
* Vincent Delecroix: Chargé de recherche CNRS: Université de Bordeaux - Directeur
* Hugo Parlier: Professeur: University of Luxembourg - Rapporteur
* Robert Cori: Professeur émérite: Université de Bordeaux - Invité
* Alexander Scott: Professeur: University of Oxford - Rapporteur
* Stéphan Thomassé: Professeur, ENS de Lyon - Examinateur

Title:* Exploring the space of colorings of a graph

*Abstract:* This thesis focuses on combinatorial reconfiguration and structural problems with a geometric flavor. To a configuration space and given an elementary operation we associate their reconfiguration graph, whose vertices are the configurations and in which two configurations are adjacent if they differ by one operation. Reconfiguration is motivated by random sampling and practical applications in statistical mechanics. It raises algorithmic, probabilistic as well as structural questions, for example by looking at the geometry of the reconfiguration graph or the complexity of the reachability problem in it. The main reconfiguration operation studied in this thesis is called a Kempe change and operates on the proper colorings of a graph. We also study other reconfiguration operations motivated by low-dimensional topology. We present several polynomial upper bounds on the diameter of the reconfiguration graph and obtain algorithmic results in various settings.

[Clément Legrand-Duchesne ] (Université de Bordeaux, LaBRI )
https://www.labri.fr/perso/clemlegrand/

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .