Combinatorial structures and algorithms in symmetric graphs

本项目的主要目标是在各种高度对称图族中推导出关于循环和其他基本结构（如路径和匹配）的新的理论结果，并实现相应的组合算法。我们项目的起点是20世纪70年代Lovász的一个著名猜想，该猜想断言，除了五个已知的例外情况外，每个连通和顶点传递的图都有一个汉密尔顿循环。一个顶点传递图是一个从任何顶点的角度来看都“看起来一样”的图，一个汉密尔顿循环是一个只访问每个顶点一次的循环。该项目的目标之一是解决Lovász猜想的几个特殊情况，这些情况也是长期存在的问题，我们最近在这方面取得了重大进展。该项目的这一部分是我们对该领域多个长期问题的早期解决方案的延续，包括20世纪80年代臭名昭著的中层猜想。此外，我们还将为计算机科学家感兴趣的不同组合对象开发新的Gray编码算法，例如位串，排列，几何构型，偏置集和多面体。解决这些问题需要结合和发展来自不同子领域的新的理论工具和技术，这些新的技术和联系将引起其他研究人员的兴趣。我们还计划实现在这个项目过程中开发的所有算法，并将它们提供给其他研究人员、学生和教育工作者。为此，我们将与其他研究人员一起重新启动组合对象服务器，这是一个由Frank Ruskey首先建立的网站。这个网站提供了一个易于使用的界面来运行、探索和下载各种基本组合算法的开源代码。

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.