Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
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 ...