Bootstrap percolation on a graph iteratively enlarges a set of occupied sites by adjoining points with at least $theta$ occupied neighbors. The initially occupied set is random, given by a uniform product measure, and we say that spanning occurs if e
very point eventually becomes occupied. The main question concerns the critical probability, that is, the minimal initial density that makes spanning likely. The graphs we consider are products of cycles of $m$ points and complete graphs of $n$ points. The major part of the paper focuses on the case when two factors are complete graphs and one factor is a cycle. We identify the asymptotic behavior of the critical probability and show that, when $theta$ is odd, there are two qualitatively distinct phases: the transition from low to high probability of spanning as the initial density increases is sharp or gradual, depending on the size of $m$.
Deterministic walk in an excited random environment is a non-Markov integer-valued process $(X_n)_{n=0}^{infty}$, whose jump at time $n$ depends on the number of visits to the site $X_n$. The environment can be understood as stacks of cookies on each
site of $mathbb Z$. Once all cookies are consumed at a given site, every subsequent visit will result in a walk taking a step according to the direction prescribed by the last consumed cookie. If each site has exactly one cookie, then the walk ends in a loop if it ever visits the same site twice. If the number of cookies per site is increased to two, the walk can visit a site infinitely many times and still not end in a loop. Nevertheless the moments of $X_n$ are sub-linear in $n$ and we establish monotonicity results on the environment that imply large deviations.
Jigsaw percolation is a nonlocal process that iteratively merges connected clusters in a deterministic puzzle graph by using connectivity properties of a random people graph on the same set of vertices. We presume the Erdos--Renyi people graph with e
dge probability p and investigate the probability that the puzzle is solved, that is, that the process eventually produces a single cluster. In some generality, for puzzle graphs with N vertices of degrees about D (in the appropriate sense), this probability is close to 1 or small depending on whether pD(log N) is large or small. The one dimensional ring and two dimensional torus puzzles are studied in more detail and in many cases the exact scaling of the critical probability is obtained. The paper settles several conjectures posed by Brummitt, Chatterjee, Dey, and Sivakoff who introduced this model.
We are interested in the spread of an epidemic between two communities that have higher connectivity within than between them. We model the two communities as independent Erdos-Renyi random graphs, each with n vertices and edge probability p = n^{a-1
} (0<a<1), then add a small set of bridge edges, B, between the communities. We model the epidemic on this network as a contact process (Susceptible-Infected-Susceptible infection) with infection rate lambda and recovery rate 1. If nplambda = b > 1 then the contact process on the Erdos-Renyi random graph is supercritical, and we show that it survives for exponentially long. Further, let tau be the time to infect a positive fraction of vertices in the second community when the infection starts from a single vertex in the first community. We show that on the event that the contact process survives exponentially long, tau |B|/(np) converges in distribution to an exponential random variable with a specified rate. These results generalize to a graph with N communities.
The d-dimensional Hamming torus is the graph whose vertices are all of the integer points inside an a_1 n X a_2 n X ... X a_d n box in R^d (for constants a_1, ..., a_d > 0), and whose edges connect all vertices within Hamming distance one. We study t
he size of the largest connected component of the subgraph generated by independently removing each vertex of the Hamming torus with probability 1-p. We show that if p=lambda / n, then there exists lambda_c > 0, which is the positive root of a degree d polynomial whose coefficients depend on a_1, ..., a_d, such that for lambda < lambda_c the largest component has O(log n) vertices (a.a.s. as n to infty), and for lambda > lambda_c the largest component has (1-q) lambda (prod_i a_i) n^{d-1} + o(n^{d-1}) vertices and the second largest component has O(log n) vertices (a.a.s.). An implicit formula for q < 1 is also given. Surprisingly, the value of lambda_c that we find is distinct from the critical value for the emergence of a giant component in the random edge subgraph of the Hamming torus. Additionally, we show that if p = c log n / n, then when c < (d-1) / (sum a_i) the site subgraph of the Hamming torus is not connected, and when c > (d-1) / (sum a_i) the subgraph is connected (a.a.s.). We also show that the subgraph is connected precisely when it contains no isolated vertices.
