group C01

Mathematics Approach for Expanding Combinatorial Reconfiguration: Toward New Methods Based on Case Studies


Founding the “mathematical theory” for combinatorial reconfiguration, and proposing new mathematical methods that are useful for combinatorial reconfiguration.

History tells us concepts in mathematics have been used to resolve problems of combinatorial reconfiguration. An old example is a solution to Sam Lloyd’s problem about the 15-puzzle by Johnson and Story. Their solution first rephrases the problem to one about permutations and then studies a homomorphism to the signs. This can be seen as an application of knowledge in group theory from the viewpoint of modern mathematics. Other applications of mathematics to combinatorial reconfiguration include hyperbolic geometry and topology.

Those are samples of the examples that bridge mathematics and combinatorial reconfiguration. On the other hand, those examples only exist sporadically, and a framework that unifies them cannot be found. Group C01 aims at sublimating common mathematical ideas that can be seen in bridges between mathematics and combinatorial reconfiguration and founding a “mathematical theory of combinatorial reconfiguration.” A final goal is to propose a new methodology for resolving problems of combinatorial reconfiguration and to make mathematics a useful tool for researchers and practitioners.