Convergence on a random graph

Question

Assume a directed graph $G = (V,E)$ is drawn from a random graph distribution, for instance Erdős–Rényi's $G(n,p)$ (but with directed edges). Let $S:V\rightarrow\mathcal{P}(V)$ be the direct successors function, that is $S(u) = (\left\{u\right\} \times V) \cap E$

Let $f_0: V\rightarrow\left\{0,1\right\}$ be an initial, arbitrary, labeling of vertices with $0$'s and $1$'s

Define $$n_t(u,x) = \left|\left(\{u\} \cup S(u)\right) \cap f_{t}^{-1}(x)\right|$$

$n_t(u,.)$ is simply the number of vertices labelled one or zero among $u$ and its direct successors. Now define recursively:

$$f_t(u) = \left\{ \begin{array}{cc} 0 & \textrm{if} & n_{t-1}(0) > n_{t-1}(1)\\ 1 & \textrm{if} & n_{t-1}(1) > n_{t-1}(0)\\ f_{t-1}(u) & \textrm{otherwise} & \end{array} \right.$$

Simply speaking, at each step $t$, a vertex's label is changed to reflect the majority among itself and its direct successors, or is unchanged in case of a tie.

I am interested in the convergence of the sequence $f_t$, and in particular convergence to a limit that is constant over $V$ (all $1$'s or all $0$'s) for all initial conditions. How is the probability of convergence affected by the statistics of the graph?

I'm sure the problem has been studied and I'd happily take some references on the topic.

Answer 1

I am not an expert in this field, but this seems related to what some people call "bootstrap percolation" and some other "cellular automata".

First have a look here for a nice simulation in the case of a finite box and classical references.

Now, in the context of $G(n,p)$ you have the paper Bootstrap percolation on the random graph $G_{n,p}$ by Janson, Łuczak, Turova, and Vallier

A recent contribution in 2d is Universality of two-dimensional critical cellular automata by Bollobás, Duminil-Copin, Morris, Smith.

Answer 2

Let $\Omega = \{0,1\}^V$ be the state space, and $T: \Omega \to \Omega$ the time evolution operator (so $f_{t+1} = T(f_t)$). Note that the evolution has a monotonicity property: if $f \le g$ (i.e. $f(u) \le g(u)$ for all $u \in V$) then $T(f) \le T(g)$. So starting from a given state we will either end up in a fixed point or a cycle that is an antichain for the partial order $\le$.

It is quite possible to have a cycle: for example, consider an undirected $4$-cycle with initial configuration $f_0 = (0,1,0,1)$. Since each vertex's two neighbours have the opposite label to itself, we get $f_1 = (1,0,1,0)$, and then again $f_2 = f_0$.

A configuration $f$ is a fixed point of $T$ if for each vertex $v$, its successors with opposite label to $v$ don't outnumber its successors with the same label as $v$ by more than $1$.

Let's consider the Erdős–Rényi model, where $p \in (0,1)$ is the probability of any given pair $(v,u)$ being an arc. Suppose $f$ is a given configuration with $k$ $0$'s and $n-k$ $1$'s, $k = n/2 + s \sqrt{n}$. For a vertex $v$ labelled $0$, the numbers of $0$'s and $1$'s among its successors are independent binomial random variables $X_0$, $X_1$ with parameters $(k-1), p$ and $n-k, p$ respectively.
$X_0 - X_1$ is then approximately normal with mean $(2k-1-n) p \approx 2 s \sqrt{n}$ and variance $(n-1) p (1-p)$. Thus $$P(T(f)(v) = f(v)) = P(X_0 + 1\ge X_1) \approx 1 - \Phi\left(\dfrac{(2k-1-n)p}{\sqrt{(n-1) p (1-p)}}\right) \approx \Phi(-s r)$$ where $\Phi$ is the standard normal random variable and $r = 2\sqrt{p/(1-p)} $. Similarly for a vertex labelled $1$, $P(T(f)(v) = f(v)) \approx \Phi(sr)$. Since the successors of different vertices are independent,

$$P(f \ \text{is a fixed point}) \approx \Phi(-sr)^{n/2} \Phi(sr)^{n/2} \approx 2^{-n} \exp(-2 r^2 s^2 n/\pi)$$ It looks to me like this will imply that the expected number of fixed points that are not all $0$ or $1$ is $O(1/\sqrt{n})$. Thus almost certainly there are no such fixed points.