Cycle decompositions of graphs and eulerian properties of hypergraphs

图的循环分解和超图的欧拉性质

• 批准号: RGPIN-2022-02994
• 负责人: Sajna, Mateja
• 金额: $ 1.97万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=759213
• 关键词: Cycle; decompositions; graphs; eulerian; properties

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.

我对图的循环分解着迷了20多年。这个充满活力的研究领域在图论和组合设计理论的交叉点，在过去的几年里取得了惊人的进展。然而，一些核心问题仍然悬而未决，而且由于最近取得的进展，这些问题现在变得更加容易解决。我的长期愿景是为这一知识体系做出重大而持久的贡献。 如果一个图的边可以着色，使得任何一种颜色的所有边的集合形成一个圈，则称该图被分解为圈。在1967年首次引入调度的背景下，中央循环分解问题之一是Oberwolfach问题。它询问会议的n个参与者是否可以坐在指定大小的圆桌旁几个晚上，以便每对参与者恰好坐在一起一次（假设桌子大小之和为n）。在数学术语中，这个问题是问一个完整的图是否可以分解成2个因子（nights），每个因子由指定长度的循环（表）组成。对于这个问题的原始版本，已知针对特定表大小的许多解决方案，然而，该问题通常仍然是开放的。在这个应用程序中，我打算研究这个问题的几个变体：配偶爱变体，蜜月变体和定向变体。前两个变量涉及n/2对夫妇;每个参与者都要坐在其他参与者旁边一次，坐在配偶旁边两次（爱配偶的变量）或每次（蜜月变量）。在有向变体中，每个参与者都要坐在其他参与者的右边一次。 此外，我建议从另一个角度来研究循环分解问题：使用一个强大的技术，分离，获得新的循环分解的完全多部图从现有的循环分解的完全多重图。我的研究计划的第二个主题是超图的欧拉性质（超图是图的推广）。众所周知，一个图允许一个欧拉环当且仅当每个顶点都是偶数度。对于超图没有类似的结果;事实上，超图的类似问题是NP-完全的（计算困难）。此外，有一个以上的自然的方式来推广的概念，欧拉巡回超图，我建议调查各种超图类的这些属性。一个给定的图分解成指定长度的圈的存在性问题是图论中一个基本的开放问题，就像超图的欧拉之旅的存在性问题一样。这两个概念是松散相关的，都可以用来模拟某些类型的调度问题。因此，所提出的工作不仅将在这些研究领域留下重要的印记，而且具有实际应用价值。