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.