14:00
17:00

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.

English
Amphi LaBRI