Turan-Type Problems and Bootstrap Percolation

This dissertation considers a Turán-type problem in extremal graph theory and critical probabilities for bootstrap percolation. The first, shorter part of the dissertation concerns extremal graph theory. In a graph G on n vertices, how many pairs of vertices can be at distance exactly k from one another if G has the property that no three vertices are pairwise at distance k? It is proved that, for k and n = n(k) sufficiently large, the largest possible number of pairs is (n − k + 1)2/4. The second, longer part of the dissertation concerns bootstrap percolation. Bootstrap percolation on the vertex set of a graph G is a cellular automaton in which vertices have two states, infected and uninfected. Initially, vertices are infected independently with probability p. Infected vertices remain infected, and an uninfected vertex becomes infected if enough neighboring vertices are infected. The precise criterion for a vertex to become infected, as well as the definition of its neighborhood, depends on the update rule in question. As p varies, there is a critical probability for the event that the initial set percolates, that is, that all of V (G) becomes infected. For most update rules, the critical probability displays a sharp threshold. Results are proved about the critical probabilities for various update rules, and in one case a sharp threshold result is proved. First, improving a result of Balogh, Bollobás, and Morris, an improved upper bound is given for the critical probability for r-neighbor bootstrap percolation in [n]d. Second, bounds are given on the critical probabilities for bootstrap percolation on Z2 for a broad family of update rules. Third, a sharp threshold result is proved for the probability that a randomly chosen set percolates in d-neighbor bootstrap percolation on Tnd, the d-dimensional discrete torus, by time t = t(n), fort = o(log n/ log log n). This is the first sharp threshold result related to bootstrap percolation for an event other than the event that the set simply percolates