Symmetry in graphs and hypergraphs

该建议的四个主要研究方向涉及图和相关结构（有向图和超图）中对称性的研究。图是由点（称为顶点）和连接顶点对的链接（称为边）组成的数学对象。图形在计算机科学和许多其他学科中被用来对诸如数据结构、通信网络、计算流、交通网络、化学分子、社交网络、生态系统等对象进行建模。图的对称性可以通过许多不同的方式来测量：通过变换（称为自同构）保持图;通过某些子结构的存在，例如，遍历每个顶点的循环（称为汉密尔顿循环）;由图可以被分解成的子结构，等等。具有高对称性的图（及其推广）在设计可靠网络以及调度问题中起着重要作用。除了应用之外，从纯理论的角度来看，这样的图是有趣和美丽的。我感兴趣的一些问题（例如，有向图分解和汉密尔顿圈的问题）是关于图的基本未解决的问题：它们的陈述简单而美丽，但很难解决;有些问题已经开放了几十年。这些问题的解决方案将提高我们的理解一些重要的代数和组合方面的图论。

The four main research directions of this proposal pertain to the study of symmetry in graphs and related structures (digraphs and hypergraphs). Graphs are mathematical objects consisting of points (called vertices) and links (called edges) that join pairs of vertices. Graphs are used in computer science and many other disciplines to model such objects as data structures, communication networks, computational flows, traffic networks, chemical molecules, social networks, ecosystems etc. I am particularly interested in graphs with a lot of symmetry. Symmetry of a graph can be measured in many different ways: via transformations (called automorphisms) that preserve the graph; by the existence of certain substructures, for example, cycles that traverse every vertex (called Hamilton cycles); by the substructures into which the graph can be decomposed, and so on. Graphs with high symmetry (and their generalizations) play an important role in designing reliable networks, as well as in scheduling problems. Apart from applications, such graphs are interesting and beautiful from a purely theoretical point of view. Some of the problems I am interested in (for example, the problems on digraph decompositions and Hamilton cycles) are basic unsolved problems about graphs: beautiful in the simplicity of their statement and yet very difficult to solve; some have been open for decades. Solutions to these problems would improve our understanding of some important algebraic and combinatorial aspects of graph theory.