Consider the following model for percolation in an infinite graph: each vertex has a certain region (set of vertices) associated with it, which at the beginning contains only the vertex itself, and grows with time. Each vertex holds a random Poisson clock, all clocks independent, and at each tick of a clock of a vertex $v$, $v$'s region is updated to the current region united with the regions of all neighbors of the $v$ (which might have grown by that time).

The question about this model is whether there exists a vertex whose region percolates = becomes infinite at a finite time with positive probability.

Does this model have a standard name and/or has been studied before?


This kind of construction comes up in various contexts, for example in analysis of the contact model, or other models for the spread of an infection or a rumour or the like. I don't know if it has a particular name.

For some graphs you could have infinite regions at finite times.

If you impose a condition that, say, the graph has bounded vertex degrees, then the probability that $v$ has an infinite region at any finite time $t$ is zero. For $u$ to be in the region of $v$ at time $t$, there needs to be a path $u=v_0, v_1, \dots, v_n=v$ and times $0 \leq t_1 \leq t_2, \dots, t_n \leq t$ such that the bell at vertex $v_i$ rings at time $t_i$. For any given such path of length $n$, the probability that the bells ring in this way is $O(t^n/n!)$ as $n\to\infty$. If each vertex has degree at most $d$, then the number of such paths of length $n$ ending at $v$ is $O((d-1)^n)$ as $n\to\infty$. Since $\sum (d-1)^n t^n/n!$ is finite, the expected size of $v$'s region at time $t$ is finite.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.