Limiting behavior of coins on a finite graph with flips activated by a full neighborhood
I have a few observations for the path graph $P_n$ that may prove useful, but I'm not bothered enough to follow them up. Each seems easy to prove by case exhaustion. These are as follows:
- Period two behaviour is the most complex that can occur (see below).
- The limiting behaviour is emerges after just two iterations. In other words, for all $v\in P_n$, $$f_2(v) = f_4(v),$$ regardless of starting configuration.
- If $f_2(v) = f_3(v) = 1$ (i.e. $f_n(v)$ is eventually 1), then $f_1(v)=f_0(v)=1$.
Stable structures
This given, you can tell all from the starting partition $f_0$ (perhaps not as simply as applying the derivation twice, but hey).
Notation:
- $1^n := \underbrace{11…1}_{n}$, and similarly,
- $0^n := \underbrace{00…0}_{n}$.
One way may be to look at the blocks:
- By block, I mean a chain of 1s which is surrounded by $0$s on each side (i.e. $01^n0$).
- Two blocks are adjacent if they are separated by just one $0$.
- A block is a middle block if it is adjacent to two blocks (one on each side).
- A block is an end block if it is adjacent to exactly one block (on the left or right).
- A block is a loner if it is surrounded by no other blocks.
(As for the ends of the graph, one may wish to add 001 and 100 artificially to the left and right end respectively for this classification and ensuing description to make consistent sense. One can subtract 4 afterwards!)
One can quickly verify what happens for middle blocks. Here, what happens to the 1s on each side depends on the length of the block it belongs to (and whether it is an end or not):
$$\begin{array}{c|c} f_0 & f_2 \\ \hline 10101 & ?000? \\ 101101 & ?0000? \\ 1011101 & ?01110? \\ \ \phantom{n\geq4, }{101^n01},\ {n\geq4} & ?010^{n-2}10? \end{array}$$
That is,
- middle blocks of lengths 1 or 2 disappear completely;
- middle blocks of length 3 survive entirely; and
- middle blocks of length 4 or more: only the endpoints survive.
(Survive here means $f_2(v)=1$, and disappear means is eventually 0.)
Similar thing holds for one-sided blocks, except one of its endpoints always survives.
Finally, only the endpoints of loner blocks survive, unless the block is length 3.
It is the surviving endpoints which satisfy $f_n(v) = 1$ for all $n$. But that's not all — whenever a vertex is between two endpoints which survive, it alternates between 0 and 1, ad infinitum. For example,
$$00111011100 \longrightarrow 00101110100 \longrightarrow 00111011100,$$
and indeed, any chain of adjacent middle blocks of length 3 has this property. More precisely, a vertex will alternate if and only if one of the following holds:
- it is between a middle block of length 3 and a block of length 3 or more.
- it is between a middle block of length 3 and an end block of length 1.
- it is the middle vertex of any block of length 3.
These are precisely the vertices which do not get deactivated (surviving endpoints and alternators), so an algorithm may focus on counting these somehow. To my mind this seems like a hard thing to do, so an estimation may be in order.
(PS. If you want my Mathematica file, do say so!)