Projects / Programmes
Traversability in vertex-transitive graphs
| Code |
Science |
Field |
Subfield |
| 1.01.00 |
Natural sciences and mathematics |
Mathematics |
|
| Code |
Science |
Field |
| P110 |
Natural sciences and mathematics |
Mathematical logic, set theory, combinatories |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
Hamilton path, Hamilton cycle, vertex-transitive graph, Cayley graph, automorphism group
Researchers (16)
Organisations (4)
Abstract
The project considers the prominent outstanding unsolved problem posed by Lovász in 1969 which ties together two seemingly unrelated concepts – traversability and symmetry:
Does every finite connected vertex-transitive graph (a graph X with its automorphism group Aut(X) acting transitively on the vertex set V(X), or a VTG for short) have a Hamilton path (a simple path visiting all vertices of the graph)?
No connected VTG without a Hamilton path is known to exist; moreover, only four connected VTGs on at least three vertices not having a Hamilton cycle – a simple cycle containing all vertices of the graph – are known so far. None of these four exceptional graphs is a Cayley graph, that is, a VTG with a regular subgroup of automorphisms (a Cayley group). This has led to a folklore conjecture that every connected Cayley graph possesses a Hamilton cycle.
In the project the problem of the existence of Hamilton paths and cycles in connected VTGs will be referred to as the HPC problem. This problem has served as one of the main catalysts in the recent development of algebraic graph theory, one of the fastest growing research areas in discrete mathematics. Cubic VTGs hold a central position in the ongoing research for an obvious reason: scarcity of edges intuitively makes it harder to find paths or cycles, which is supported by the fact that all known VTGs without Hamilton cycles are cubic.
The project aim is to make significant contribution to the HPC problem with special emphasis given to existence of Hamilton cycles in Cayley graphs.
Significance for science
This proposal draws from certain parts of the PI application for the ERC Consolidator Grant Open Call 2017 which on the interval A-B-C received a B mark. The original ERC proposal was a 5-year proposal with a total budget of 1.3 million EUR, whereas this ARRS project proposal is a 3-year proposal with a budget of 300.000 EUR. This explains why only parts of the original ERC Consolidator Grant proposal are included in this proposal. Among other the ARRS support for this project will enable us to improve on the PI application to ERC Grant Open Call in the future. Furthermore, the results obtained within this project will serve as a basis for new directions in the pursuit of the solution to one of the most important open problems in algebraic graph theory.
Significance for the country
This proposal draws from certain parts of the PI application for the ERC Consolidator Grant Open Call 2017 which on the interval A-B-C received a B mark. The original ERC proposal was a 5-year proposal with a total budget of 1.3 million EUR, whereas this ARRS project proposal is a 3-year proposal with a budget of 300.000 EUR. This explains why only parts of the original ERC Consolidator Grant proposal are included in this proposal. Among other the ARRS support for this project will enable us to improve on the PI application to ERC Grant Open Call in the future. Furthermore, the results obtained within this project will serve as a basis for new directions in the pursuit of the solution to one of the most important open problems in algebraic graph theory.
Most important scientific results
Interim report
Most important socioeconomically and culturally relevant results
Interim report
