On certain problems in extremal and additive combinatorics

Abstract

This thesis consists of five chapters. The first chapter serves as an introduction, presenting the four problems studied in this thesis, and the results obtained. Each subsequent chapter then treats a separate problem. The second chapter is about the existence of partial isomorphisms (i.e. bijective maps that preserve only a finite number of algebraic relations) between subsets of F_p and subsets of C. The main result states that for any sufficiently small subset of F_p one can find a subset of C that algebraically behaves similarly. This has several applications, most importantly, it is shown that for small subsets of F_p, the Szemerédi-Trotter theorem holds with optimal exponent 4/3. Another application is towards an old question of A. Rényi concerning the number of terms of the square of a polynomial. The third chapter is about Turán densities of hypergraphs. The study of Turán densities was initiated by P. Turán in the 1940s, and has been an active area of research ever since. My main result proves that the set of Turán densities forms a non-trivial semigroup. Using this property several facts about Turán densities (which were previously proved by others) can be deduced in a streamlined fashion. The fourth chapter is about the Graceful Tree Conjecture, a generalization due to A. Rosa of the Ringel-Kotzig conjecture, with important ramifications in the field of graph decompositions. The main theorem is a proof of an approximative version of the conjecture for trees of bounded degree. The results in this chapter are joint work with Anna Adamaszek, Michal Adamaszek, Peter Allen and Jan Hladký. The fifth chapter is about the Towers of Hanoi problem with p pegs, a well-known variation on the classic puzzle of É. Lucas with 3 pegs. The question of determining the minimum number of moves needed to solve the puzzle has remained open for decades. Only recently a complete solution of the case of 4 pegs has been obtained by T. Bousch. The main result of the chapter is an asymptotic improvement on the best known lower bound for the minimum number of moves needed when p >= 5.

Diese Dissertation besteht aus fünf Kapiteln. Das erste Kapitel stellt die vier Probleme vor, welche Gegenstand der Dissertation sind. Jedem der vier Probleme ist eines der folgenden Kapitel gewidmet. Das zweite Kapitel befasst sich mit dem ersten Problem, der Existenz von partiellen Isomorphismen (bijektive Abbildungen, die nur eine endlich bestimmte Menge von algebraischen Relationen erhalten) zwischen Teilmengen von F_p und Teilmengen von C. Wir zeigen, dass für jede genügend kleine Teilmenge von F_p eine Teilmenge von C existiert, die sich algebraisch ähnlich verhält. Wir gehen auf einige Anwendungen dieses Ergebnisses ein, insbesondere zeigen wir, dass für kleine Teilmengen von F_p der Satz von Szemerédi--Trotter mit optimaler Potenz 4/3 gilt. Außerdem geben wir einige Teilantworten auf eine alte Frage von A. Rényi. Das dritte Kapitel befasst sich mit dem zweiten Problem, Turán-Dichten von Hypergraphen bestimmen. Dieses Problem führte zu einem klassiches Gebiet der Graphentheorie, in welchem es noch zahlreiche ungelöste Probleme gibt. Unser Hauptergebnis sagt aus, dass eine abstrakte algebraische Struktur über der Menge der Turán Dichten existiert. Hieraus folgen auf einfache Weise einige bekannte Resultate. Das vierte Kapitel befasst sich mit dem dritten Problem, der Graceful-Tree-Vermutung, eine fünfzig Jahre alte Vermutung mit wichtigen Anwendungen im Gebiet der Graphen-Zerlegungen. Unser Hauptergebnis ist eine approximative Version der Vermutung für Bäume mit beschräktem Grad. Die Ergebnisse im vorstehenden Kapitel sind in Zusammenarbeit mit Anna Adamaszek, Michal Adamaszek, Peter Allen und Jan Hladký entstanden. Das fünfte Kapitel befasst sich mit dem vierten Problem, einer Verallgemeinerung des Türme-von-Hanoi-Spiels von É. Lucas mit 3 Stäben auf die Situation mit p >= 3 Stäben. Konkret ist die Frage nach der Anzahl von Zügen, die für ein erfolgreiches Spiel notwendig sind, eine Frage, die seit einigen Jahrzehnten offen ist. Erst kürzlich ist eine Lösung für den Fall p=4 von T. Bousch erschienen. Unser Hauptergebnis ist eine verbesserte untere Schranke für die minimale Anzahl von notwendigen Zügen für den Fall p >= 5.