As part of my graduate research I am currently studying the last section in the paper "Random Majority Percolation" by Balister, Bollobas et al. The paper itself is very complicated but the last two pages are self-contained and treat an extremal question about small percolating sets (dynamic monopolies). I am wondering whether there is an obvious mistake in their last Theorem 27 or whether I am missing a detail.
Let me first present the general setup. The $d-$dimensional torus $T_n^d$ corresponds to the finite lattice $(Z/nZ)^d$, where two vertices are adjacent if and only if their "coordinates" differ by one (mod $n$). To the vertices we associate a configuration $\omega$ from a binary state space $\{0,1\}^{n^d}$, i.e. every vertex is either $1$ (active) or $0$ (inactive). Given an initial configuration $\omega$, the states of the vertices are then changed simultaneously in discrete time steps according to some rule $f$. The model is known also in the context of cellular automata.
The big question is:
How many active vertices do we need in the initial configuration so that after repeated application of the rule $f$, eventually every vertex becomes active?
This is known in literature also as percolation, and we say a configuration percolates (under some rule) if it has the property that it "makes the whole graph active".
The authors consider the following rules $f$:
- Majority rule: every vertex adapts its state to the majority of states in its neighborhood. In case of a tie, a vertex keeps its current state.
- The $r-$threshold rule, where each vertex is $1$ if and only if at least $r$ of its neighbors are active and $0$ otherwise.
- The $r-$monotone rule, where each vertex is $1$ if it has at least $r$ active neighbors and does not change its state otherwise.
Note that, given some graph, every configuration that percolates under the $r-$threshold rule also percolates under the $r-$monotone rule.
In Theorem 25 a lower bound is given for regular graphs for the minimum number of active vertices in a percolating configuration under the $r-$monotone rule. Since $T_n^d$ is a $2d-$regular graph, this lower bound applies. The authors then say this bound is tight on $T_n^d$ for $d<r<2d-1$ by giving a construction in Theorem 26. In particular, they seem to require that $T_n^d$ is $2d-$regular, since otherwise their bound from Theorem 25 was not tight.
In Theorem 27 they claim that the same construction also works for the $(d+1)-$threshold rule. Note again that a lower bound for the $r-$monotone rule is also a lower bound for the $r-$threshold rule, but identical bounds would be surprising since the first rule is "stronger" in some sense. Their very short argument however uses that every vertex is in its own neighborhood, i.e. that every vertex has a self-loop. But this was not specified. Moreover, if it was the assumption then the bound from Theorem 25 was not tight, because now we were talking about a $(2d+1)-$regular "torus". Their proof only seems to work for the majority rule, not for the $(d+1)-$threshold rule. Figure 5 on p.338 and its caption also suggest that the intention was to state a result about the majority rule, not for the $(d+1)-$threshold rule. I think that these are two different rules on $T_n^d$ (without self loops). In both cases, a vertex becomes active if it has at least $d+1$ active neighbors, but under the majority rule an active vertex requires only $d$ active neighbors to stay active in the next step, as opposed to the $(d+1)-$threshold rule where it needs at least $d+1$ active neighbors.
I also think that it is not too hard to show that in the case $d=2,r=3$ the lower bound for an $r-$threshold percolating set is in fact strictly larger than what they claim. Am I right to assume that there is a mistake in the statement of their Theorem 27 or am I missing a detail?
