Combinatorial structures and algorithms in symmetric graphs

点击翻译按钮获取中文摘要

The main goal of this project is to derive new theoretical results about cycles and other fundamental structures such as paths and matchings in various families of highly symmetric graphs, and to implement the corresponding combinatorial algorithms. The starting point of our project is a famous conjecture due to Lovász from the 1970s, which asserts that every connected and vertex-transitive graph has a Hamilton cycle, apart from five known exceptions. A vertex-transitive graph is a graph that ‘looks the same’ from the point of view of any vertex, and a Hamilton cycle is a cycle that visits every vertex exactly once. One of the goals of this project is to tackle several special cases of Lovász’ conjecture that are also long-standing problems, and for which we recently made significant progress. This part of the project is a continuation of our earlier solutions of multiple long-standing problems in this area, including the notorious middle levels conjecture from the 1980s. Moreover, we will also develop new Gray code algorithms for different combinatorial objects of interest for computer scientists, such as bitstrings, permutations, geometric configurations, posets and polytopes. Solving these problems requires to combine and develop new theoretical tools and techniques from different subareas, and these new techniques and connections will be of interest for other researchers. We also plan to implement all the algorithms developed in the course of this project, and to make them available for other researchers, students and educators. For this purpose, jointly with other researchers, we will relaunch the Combinatorial Object Server, a website first established by Frank Ruskey. This website provides an easy-to-use interface to run, explore and download open-source code for various fundamental combinatorial algorithms.