[00324] Minisymposium on Combinatorial Reconfiguration
Session Time & Room : 2E (Aug.22, 17:40-19:20) @G302
Type : Proposal of Minisymposium
Abstract : Combinatorial reconfiguration is an emerging branch of discrete mathematics that deals with gradual changes of combinatorial objects. While several related concepts have been studied over the years from different perspectives, the theory is growing up by combining its mathematical, computational and practical aspects.
This minisymposium aims at communicating recent research trends on combinatorial reconfiguration and discussing possible future directions.
[04748] Invitation to Combinatorial Reconfiguration
Format : Talk at Waseda University
Author(s) :
Takehiro Ito (Tohoku University)
Abstract : Combinatorial Reconfiguration studies reachability and related questions over combinatorial structures. A typical example asks if the solution space of a Boolean formula is connected with respect to the Boolean cube topology, formed by flipping one bit at the time. Reconfiguration problems have been studied intensively in this decade from the algorithmic viewpoints. In this talk, we will give a broad introduction of combinatorial reconfiguration, and show some recent progress on the topic.
[04759] Geometric algorithms for reconfiguring modular robots
Format : Online Talk on Zoom
Author(s) :
Irene Parada (BarcelonaTech (UPC))
Abstract : Modular self-reconfigurable robots consist of units that can move and connect to form larger shapes. A central problem is how to efficiently reconfigure between shapes while maintaining connectivity. We explore the computational complexity of this reconfiguration problem for the most fundamental lattice-based models of modular robots. Some lattices and moves allow for efficient reconfiguration algorithms, while in other models the problem is PSPACE-complete. For those cases, we identify simple conditions that guarantee universal reconfigurability.
[05218] Toric Promotion and Permutoric Promotion
Format : Online Talk on Zoom
Author(s) :
Colin Defant (Massachusetts Institute of Technology)
Abstract : We introduce toric promotion and, more generally, permutoric promotion operators. These operators, which are variants of Schutzenberger's famous promotion operator, act on labelings of a graph. We highlight cases where these operators have surprisingly nice orbit structures. Our investigation of permutoric promotion is surprisingly involved and relies on the analysis of gliding globs, sliding stones, and colliding coins. This work on permutoric promotion is joint with Rachana Madhukara and Hugh Thomas.
[04747] Triangulations of cyclic polytopes through the lens of reconfiguration
Format : Talk at Waseda University
Author(s) :
Nicholas James Williams (Lancaster University)
Abstract : We discuss the reconfiguration problem given by taking the set of triangulations of a cyclic polytope as the state space, with the reconfiguration moves given by bistellar flips (the higher-dimensional analogue of flipping a diagonal within a quadrilateral). The state space is connected, and we will outline how this is proven using a certain partial order on the states called the higher Stasheff-Tamari order. We will further consider as many different other aspects of the reconfiguration as time permits, including the significance of triangulations of higher-dimensional cyclic polytopes for reconfigurations of lower-dimensional cyclic polytopes, efficient combinatorial descriptions of triangulations of cyclic polytopes, and the diameter of the state space.
