Grant: Discovery Grants Program - Individual
University of Ottawa
$22,000.00
Cycle decompositions of graphs and related problems
FY 2017-18
Summary
I have been fascinated by cycle decompositions of graphs for nearly 20 years. This vibrant research area on 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 a number of round tables of specified sizes for k 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 wide open. In this research plan, I am proposing to solve two new variants of the problem, primarily for equal table sizes. I also intend to investigate a version of the Oberwolfach Problem for complete symmetric equipartite digraphs, as well as study cycle decomposition problems from another point of view: using a technique called amalgamation-detachment to obtain new cycle decompositions of complete multipartite graphs from existing cycle decompositions of complete multigraphs. The second topic of my research proposal eulerian properties of hypergraphs is related to the first since a connected graph admits a decomposition into cycles (of lengths that cannot be predetermined) if and only if it admits an Euler tour (cyclic traversal of the graph that encounters each edge exactly once). 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, it has recently been shown that the analogous problem is NP-complete even for some restricted subclasses of hypergraphs. 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 a (strict) Euler tour of a hypergraph. The two concepts are related, and both can be used to model certain types of scheduling. Thus, I anticipate that the proposed work will not only leave a significant mark on this research area, but also find practical applications.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2016-04798
Name nom
Sajna, Mateja
Department département
Mathematics and Statistics - Mathématiques et statistiques
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2016
Award amount
22000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
2
Nb partie
5
Application title
Cycle decompositions of graphs and related problems
Keyword
NSERC
Application summary
I have been fascinated by cycle decompositions of graphs for nearly 20 years. This vibrant research area on 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 a number of round tables of specified sizes for k 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 wide open. In this research plan, I am proposing to solve two new variants of the problem, primarily for equal table sizes. I also intend to investigate a version of the Oberwolfach Problem for complete symmetric equipartite digraphs, as well as study cycle decomposition problems from another point of view: using a technique called amalgamation-detachment to obtain new cycle decompositions of complete multipartite graphs from existing cycle decompositions of complete multigraphs. The second topic of my research proposal eulerian properties of hypergraphs is related to the first since a connected graph admits a decomposition into cycles (of lengths that cannot be predetermined) if and only if it admits an Euler tour (cyclic traversal of the graph that encounters each edge exactly once). 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, it has recently been shown that the analogous problem is NP-complete even for some restricted subclasses of hypergraphs. 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 a (strict) Euler tour of a hypergraph. The two concepts are related, and both can be used to model certain types of scheduling. Thus, I anticipate that the proposed work will not only leave a significant mark on this research area, but also find practical applications.