Projects / Programmes
EXPLORATION OF THE INTRINSIC STRUCTURE OF TOWER GRAPHS
| Code |
Science |
Field |
Subfield |
| 1.01.05 |
Natural sciences and mathematics |
Mathematics |
Graph theory |
| Code |
Science |
Field |
| P001 |
Natural sciences and mathematics |
Mathematics |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
discrete mathematics; graph theory; theoretical computer science; Tower of Hanoi problem; tower graphs; Sierpiński graphs; integer sequences
Researchers (18)
Organisations (2)
Abstract
The main goal of the project is to deepen the understanding of Hanoi graphs, Sierpiński graphs, and related classes of graphs. The specific topics we plan to cover are 1. Metric properties of tower graphs; 2. Algorithms and computer experiments on tower graphs; 3. Structural properties of tower graphs; 4. Investigation of tower graphs relevant in (neuro-)psychology and elsewhere; 5. Classification of Sierpiński-like graphs; and 6. Second edition of the book ''The Tower of Hanoi—Myths and Maths''.
The core of our research will be performed in the classical theorem-proof manner. However, due to the delicate structure of Hanoi graphs we will also concentrate on numerical evidence to obtain eventually provable results. The main goal of our computational experiments will be to compute distances and metric invariants in Hanoi graphs. We will also employ computer experiments for the Star Tower of Hanoi graphs and for different structure properties of Hanoi and Sierpiński graphs, like for instance the packing chromatic number of Sierpiński graphs.
Our plan is to investigate invariants and other problems on Sierpiński graphs and related classes of graphs, including those in the general framework introduced by Hasunuma, that are of recent interest to the research community. In this way we will deepen the understanding of these classes of graphs and at the same time open them to other researchers. The problems that we plan to attack include complexity (that is, the number of spanning trees), the number of matchings, the packing chromatic number, and the game domination number.
For Hanoi graphs the situation is much more delicate. For instance, no 1-perfect codes exist in non-trivial Hanoi graphs and many graph invariants which were determined for Sierpiński graphs are still unknown for Hanoi graphs, such as the domination number and the independence number. Our plan is to attack these invariants and obtain good upper and lower bounds for them because it seems that exact values are intrinsically difficult to obtain.
The Tower of London is the central solitaire game used by (neuro-)psychologists to test cognitive abilities. Since most graph invariants are unknown for London graphs (for instance, already the calculation of their sizes leads to intriguing number theoretical questions), our primary goal is to determine (or to bound) graph invariants of those London graphs which are of interest for (neuro-)psychologists.
Tower graphs are also applicable elsewhere. A couple of months ago, chemical self-assembly of ''Sierpiński triangles'' was reported on. Our goal with respect to this application is to understand the self-assembly and to see how our understanding of Sierpiński-like graphs can be used to make new insights into this application.
Graphs whose drawings can be viewed as approximations to the famous Sierpiński triangle have been studied intensely in the past 25 years in numerous different scientific areas. Therefore it is not surprising that different names have been used for the same object and the same name for different objects. Our aim is to bring some order into this zoo of Sierpiński-like graphs and to summarize the properties of the most important species.
The second edition of the book ''The Tower of Hanoi—Myths and Maths'' is also planned. It will contain a number of updates, but also some more introductory topics from discrete mathematics and mathematics general in order to be more suitable for classroom usage. The second edition was in particular triggered by progress on a problem open for more than a century. This development, initiated by Thierry Bousch from Paris, will be a central topic of our project. We are in contact with the author and may wish to incorporate him into our own efforts.
Significance for science
The project belongs to basic research in the area of mathematics and related fields such as computer science. Problems that we will work on are internationally important, which can in particular be justified by our bibliography from the last period as well as with the impact of our results. The problems we plan to attack are central in the area and at the same time have applications in other scientific fields, for instance in neuro-psychology and in chemistry.
The problems that we propose to investigate are not only unsolved, but having in mind the extended recent interest into Sierpiński graphs (including Hanoi graphs), they are also relevant. We expect to publish several papers in key journals from the area of discrete mathematics related to the topics of the proposed project. We will also present our results at relevant international conferences. The work on the project will serve as a perfect basis for a second edition of the 2013 Springer book The Tower of Hanoi—Myths and Maths. That the second edition is a desirable and realistic goal of the project can be justified by the recent very quick development of the area and by a dozen of very positive reviews that the book has received. Also, the large scale computer experiments can serve as a model for future algorithms and computational methods.
Significance for the country
The proposed project is in the area of pure mathematics, therefore it is difficult to measure its direct impact on the economy and society. However, the project is oriented to encourage the integration of young researchers and students into its activities. In this way it allows for a long-term continuation of the research quality in mathematics, which in turn has an important impact on the quality of the university programs in mathematics and other sciences. As a direct impact of the project we can also consider the fact that it supports a continuation of research contacts of Slovenian scientists with the most up-to-date developments.
Most important scientific results
Interim report,
final report
Most important socioeconomically and culturally relevant results
Interim report,
final report
