This is the first comprehensive monograph on the mathematical theory of the solitaire game "The Tower of Hanoi" which was invented in the 19th century by the French number theorist Édouard Lucas. The book comprises a survey of the historical development from the gameʼs predecessors up to recent research in mathematics and applications in computer science and psychology. Apart from long-standing myths it contains a thorough, largely self-contained presentation of the essential mathematical facts with complete proofs, including also unpublished material. The main objects of research today are the so-called Hanoi graphs and the related Sierpiński graphs. Acknowledging the great popularity of the topic in computer science, algorithms and their correctness proofs form an essential part of the book. In view of the most important practical applications of the Tower of Hanoi and its variants, namely in physics, network theory, and cognitive (neuro)psychology, other related structures and puzzles like, e.g., the Tower of London, are addressed. Numerous captivating integer sequences arise along the way, but also many open questions impose themselves. Central among these is the famed Frame-Stewart conjecture. Despite many attempts to decide it and large-scale numerical experiments supporting its truth, it remains unsettled after more than 70 years and thus demonstrates the timeliness of the topic. Enriched with elaborate illustrations, connections to other puzzles and challenges for the reader in the form of (solved) exercises as well as problems for further exploration, this book is enjoyable reading for students, educators, game enthusiasts and researchers alike.
COBISS.SI-ID: 16565337
We introduce and investigate bucolic complexes, a common generalization of systolic complexes and CAT(0) cubical complexes. They are defined as simply connected prism complexes satisfying some local combinatorial conditions. We study various approaches to bucolic complexes: from graph-theoretic and topological perspectives, as well as from the point of view of geometric group theory. In particular, we characterize bucolic complexes by some properties of their 2-skeleta and 1-skeleta (that we call bucolic graphs), by which several known results are generalized. We also show that locally-finite bucolic complexes are contractible, and satisfy some nonpositive-curvature-like properties.
COBISS.SI-ID: 16633177
Protein structures evolved through a complex interplay of cooperative interactions, and it is still very challenging to design new protein folds de novo. Here we present a strategy to design self-assembling polypeptide nanostructured polyhedra based on modularization using orthogonal dimerizing segments. We designed and experimentally demonstrated the formation of the tetrahedron that self-assembles from a single polypeptide chain comprising 12 concatenated coiled coil–forming segments separated by flexible peptide hinges. The path of the polypeptide chain is guided by a defined order of segments that traverse each of the six edges of the tetrahedron exactly twice, forming coiled-coil dimers with their corresponding partners. The coincidence of the polypeptide termini in the same vertex is demonstrated by reconstituting a split fluorescent protein in the polypeptide with the correct tetrahedral topology. Polypeptides with a deleted or scrambled segment order fail to self-assemble correctly. This design platform provides a foundation for constructing new topological polypeptide folds based on the set of orthogonal interacting polypeptide segments.
COBISS.SI-ID: 5222682
A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show the surprising fact that it is NP-hard to compute the crossing number of near-planar graphs. A graph is 1-planar if it has a drawing where every edge is crossed by at most one other edge. We show that it is NP-hard to decide whether a given near-planar graph is 1-planar. The main idea in both reductions is to consider the problem of simultaneously drawing two planar graphs inside a disk, with some of its vertices fixed at the boundary of the disk. This leads to the concept of anchored embedding, which is of independent interest. As an interesting consequence we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. This resolves a question of Hliněný.
COBISS.SI-ID: 16733017
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph $G$ is minimal if the graph $G-e$ is 1-planar for every edge $e$ of $G$. We construct two infinite families of minimal non-1-planar graphs and show that for every integer $n \geq 63$, there are at least $2^{(n-54)/4}$ nonisomorphic minimal non-1-planar graphs of order $n$. It is also proved that testing 1-planarity is NP-complete.
COBISS.SI-ID: 16557401