Graph bootstrap percolation and additive combinatorial constructions

Abstract

Given a (usually small) graph H and an n-vertex graph G the H-bootstrap process on G is defined to be the sequence of graphs which starts with G and in which each graph is obtained from the previous one by adding every edge that completes a copy of H. This process eventually stabilises. We investigate the maximum running time of the process, which is the largest number of steps an H-bootstrap process on an n-vertex graph can take before it has stabilised, for several choices of H and initiate the study of which graph parameters determine the asymptotic growth of that number as a function of n. The first range of running times we consider is characterised by the question "For which H is the largest number of steps asymptotically sublinear?". Here we will see graphs such as trees and cycles, and we will provide sufficient conditions which guarantee that H does not have sublinear maximum running time. On the other hand we examine those H for which the maximum running time is asymptotically much larger than n. Within the superlinear range we will encounter graphs of high connectivity or high density, but also sparse graphs such as when H is distributed as the Erdős-Rényi random graph for certain edge probabilities. We put particular emphasis on graphs with quadratic maximum running time. To provide quadratic bounds we will generalise a construction introduced by Balogh, Kronenberg, Pokrovskiy, and Szabó to study the case when H is a complete graph.

Extremal constructions from additive combinatorics provide some of the best-known lower bounds on running times in graph bootstrap percolation. In the second part of the thesis we focus on an extremal additive problem. We study sets of natural numbers with the property that for some h ≥ 2, the distance between any two distinct sums of h elements is at least a fixed power of the largest summand. By elaborating on a construction of Cilleruelo we give an infinite set that satisfies the condition above and whose counting function provides an improvement over the greedy construction.

Finally, we consider the problem of splitting matchings. Given a k-regular graph whose edge set is the union of k perfect matchings, we want to find a matching M that intersects each of the original matchings in a given number of edges. We are particularly interested in the situation in which a suitable M exists no matter what the initial matchings are. This question was introduced by Arman, Rödl, and Sales. Two special cases are fair splits and perfect splits. In the former case one takes the same number of edges from each of the original matchings, while in the latter M is itself perfect. We give necessary conditions on the existence of perfect splits as well as fair splits, and provide sufficient conditions for the case k=3.

Zu einem Graphen H und einem Graphen G mit n Knoten definieren wir den H-Bootstrap-Prozess auf G als die Folge von Graphen, die mit G beginnt und in der jeder Graph aus dem vorherigen hervorgeht, indem wir jede Kante, die eine Kopie von H vervollständigt, hinzufügen. Nach einer gewissen Anzahl an Schritten werden keine weiteren Kanten mehr hinzugefügt. Wir untersuchen für verschiedene H die maximale Laufzeit eines solchen Prozesses, welche als die größtmögliche Anzahl an Schritten definiert ist, die ein H-Bootstrap-Prozess auf einem Graphen mit n Knoten benötigt, bevor er stabil wird, und begründen das Studium der Graphenparameter, welche das asymptotische Wachstum der maximalen Laufzeit als Funktion von n bestimmen. Der sublineare Bereich ist durch die Frage "Für welche H ist die maximale Laufzeit asymptotisch kleiner als n?" gegeben. Wir zeigen, dass dieser Graphen wie etwa Bäume und Kreise umfasst, und präsentieren Bedingungen, die garantieren, dass H nicht zum obigen Bereich gehört. Ferner betrachten wir den superlinearen Bereich, welcher durch die Frage, ob die maximale Laufzeit asymptotisch größer als n ist, bestimmt wird. Hier begegnen wir Graphen mit hoher Zusammenhangszahl, aber auch den Erdős-Rényi-Zufallsgraphen für kleine Kantenwahrscheinlichkeiten. Eine für uns besondere Rolle nehmen Graphen mit quadratischer maximaler Laufzeit ein. Um quadratische Schranken zu erhalten, verallgemeinern wir zwei Konstruktionen, die von Balogh, Kronenberg, Pokrovskiy und Szabó zur Untersuchung des Falls, dass H ein vollständiger Graph ist, eingeführt wurden.

Konstruktionen aus der additiven Kombinatorik liefern mehrere der derzeit besten unteren Schranken für die maximale Laufzeit von Bootstrap-Prozessen. Im zweiten Teil dieser Arbeit untersuchen wir Mengen natürlicher Zahlen mit der Eigenschaft, dass der Abstand zwischen zwei verschiedenen aus h ≥ 2 Elementen gebildeten Summen stets mindestens eine feste Potenz des größten Summanden beträgt. Unter Nutzung einer Konstruktion von Cilleruelo beschreiben wir eine unendliche Menge, die den obigen Bedingungen genügt und deren Zählfunktion eine Verbesserung gegenüber der gierigen Konstruktion darstellt.

Schließlich betrachten wir das Problem des Teilens von Matchings. Zu einem k-regulären Graphen, dessen Kantenmenge die Vereinigung k perfekter Matchings ist, suchen wir ein Matching M, das jedes der gegebenen Matchings in einer festgelegten Anzahl von Kanten schneidet. Wir interessieren uns für jenen Fall, in dem ein geeignetes M unabhängig von der Wahl der ursprünglichen Matchings existiert. Diese Fragestellung geht zurück auf Arman, Rödl und Sales. Zwei Spezialfälle sind faire Aufteilungen und perfekte Aufteilungen. Bei Ersteren enthält M aus jedem der anfänglichen Matchings dieselbe Anzahl an Kanten, während in Letzteren M selbst perfekt ist. Wir präsentieren eine notwendige Bedingung für die Existenz solcher Aufteilungen, und ergänzen dies für k=3 um eine hinreichende Bedingung.