Minisymposium on Combinatorial Reconfiguration in ICIAM 2023
| Date and time: | 2023.08.22 Tue. 17:40-19:20
|
|---|---|
| Venue: | Waseda University, Tokyo, Japan |
| Speaker: | |
| Title: | |
| Summary: | As a part of the research project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration" (head investigator: Takehiro Ito), we are going to organize a minisymposium on Combinatorial Reconfiguration in the 10th International Congress on Industrial and Applied Mathematics (ICIAM 2023). This minisymposium aims at communicating recent research trends on combinatorial reconfiguration and discussing possible future directions.
Talk Titles and Abstracts
Title: Invitation to Combinatorial Reconfiguration
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 motivation from a variety of fields such as puzzles, statistical physics and industry, and 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.
Title: Geometric Algorithms for Modular Robotics
Abstract: Modular self-reconfigurable robots consist of individual units that can move and connect to one another to form a larger, more complex shape. A central problem that arises is how to efficiently reconfigure these robots from one shape to another while maintaining connectivity.
We will explore the computational complexity of the reconfiguration problem for the most fundamental lattice-based models of modular robots. Specifically, we will examine how the reconfiguration problem differs depending on the lattice and movement capabilities of the units. We will discuss efficient algorithms for universal reconfiguration in some models, while in others the problem is PSPACE-complete, which means that it is computationally intractable. For those cases, we identify simple conditions that allow for efficient reconfiguration.
Overall, this talk will provide insights into the challenges of reconfiguring modular robots and demonstrate how geometric and graph algorithms can help us tackle this problem.
Title: Toric Promotion and Permutoric Promotion
Abstract: We introduce toric promotion as a cyclic variant of Schutzenberger's famous promotion operator. Toric promotion acts on the labelings of a graph G; it is defined as the composition of certain toggle operators, listed in a natural cyclic order. We will show that the orbit structure of toric promotion is surprisingly nice when G is a forest. We then consider more general permutoric promotion operators, which are defined as compositions of the same toggle operators, but in permuted orders. When G is a path graph, we provide a complete description of the orbit structures of all permutoric promotion operators, showing that they satisfy the cyclic sieving phenomenon. Our proof is surprisingly involved and relies on the analysis of gliding globs, sliding stones, and colliding coins. The work on permutoric promotion is joint with Rachana Madhukara and Hugh Thomas.
Title: Triangulations of Cyclic Polytopes Through the Lens of Reconfiguration
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.
Organizers
|
Update:2023.08.09