Cycle decompositions of graphs and eulerian properties of hypergraphs

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

I have been fascinated by cycle decompositions of graphs for over 20 years. This vibrant research area in the intersection of graph theory and the theory of combinatorial designs has made breathtaking progress in the last few years. Nevertheless, some central problems remain open and have now become more accessible because of the recent advances. It is my long-term vision to make a significant and lasting contribution to this body of knowledge. A graph is said to be decomposed into cycles if its edges can be coloured so that the collection of all edges of any one colour forms a cycle. One of the central cycle decomposition problems, first introduced in 1967 in the context of scheduling, is the Oberwolfach Problem. It asks whether n participants at a conference can be seated at round tables of specified sizes for several nights so that each pair of participants sit next to each other exactly once (assuming that the table sizes add up to n). In mathematical terms, the problem asks whether a complete graph can be decomposed into 2-factors (nights), each consisting of cycles (tables) of specified lengths. For this original version of the problem, many solutions are known for specific table sizes, however, the problem is in general still open. In this application, I am proposing to investigate several variations of the problem: the spouse-loving variant, the honeymoon variant, and the directed variant. The first two variants involve n/2 couples; each participant is to sit next to every other participant exactly once, and next to their spouse exactly twice (the spouse-loving variant) or every time (the honeymoon variant). In the directed variant, each participant is to sit to the right of every other participant exactly once. In addition, I propose to study cycle decomposition problems from another point of view: using a powerful technique, detachment, to obtain new cycle decompositions of complete multipartite graphs from existing cycle decompositions of complete multigraphs. The second topic of my research proposal is eulerian properties of hypergraphs (which are a generalization of graphs). It is well known that a graph admits an Euler tour if and only if every vertex has even degree. No similar results are known for hypergraphs; in fact, the analogous problem for hypergraphs is NP-complete (computationally hard). Moreover, there is more than one natural way to generalize the notion of an Euler tour to hypergraphs, and I propose to investigate various classes of hypergraphs with respect to these properties. The question of existence of a decomposition of a given graph into cycles of specified lengths is a fundamental open problem in graph theory, as is the question of existence of an Euler tour of a hypergraph. The two concepts are loosely related, and both can be used to model certain types of scheduling problems. Thus, the proposed work will not only leave a significant mark on these research areas, but also has practical applications.