Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
Abstract
Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph G begin in one of two states, “dormant” or “active”. Given a fixed positive integer r, a dormant vertex becomes active if at any stage it has at least r active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices A, we say that G r- percolates (from A) if every vertex in G becomes active after some number of steps. Let m(G, r) denote the minimum size of a set A such that G r-percolates from A.
Bootstrap percolation has been studied in a number of settings, and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree-based density conditions that ensure m(G, 2) = 2. In particular, we give an Ore-type degree sum result that states that if a graph G satisfies σ2(G) ≥ n − 2, then either m(G, 2) = 2 or G is in one of a small number of classes of exceptional graphs. (Here, σ2(G) = min{d(x)+ d(y) : xy ∈/ E(G)}.) We also give a Chvátal-type degree condition: If G is a graph with degree sequence d1 ≤ d2 ≤ · · · ≤ dn such that di ≥ i + 1 or dn−i ≥ n − i − 1 for all 1 ≤ i < n , then m(G, 2) = 2 or G falls into one of several specific exceptional classes of graphs. Both of these results are inspired by, and extend, an Ore-type result in [D. Freund, M. Poloczek, and D. Reichman, Contagious sets in dense graphs, to appear in European J. .]
Comments
This is a manuscript made available through arxiv: https://arxiv.org/abs/1610.04499.