Let $G$ is finite graph, and there is state $0$ or $1$ for each vertex of $G$.
For each vertex $v$, let $N(v)$ be set of $v$ and vertices in the 1-neighborhood of $v$.
In the next phase, for each vertex $v$, state of $v$ is changed to majority state in $N(v)$. (If the number is tied, state of v is not changed.)
For example, see attached picture below.
In the top case, $10/01$ and $01/10$ appear alternately in period $2$.
In the bottom case, $1/11/11$ appear permanently.
I want to prove that every graph ultimately converge to alternating in period $2$ or never changing. I don't have any plausible result. If you give me some idea, I'll be happy.
Thank you.
+) Is this kind of dynamical system already known? If you know information relevant to this system, please give me some link.
[Added as an afterthought]
I solved the problem by myself.
I want to explain my solution, but It is hard for me to write formal proof.
So I write just sketch of proof.
(1) It is easy to show there is period $k$ because there is only finite possible states.
(2) For each vertex $v$, define
$s(v)$ : sequence of $0$, $1$ showing state of $v$ in period $k$. (or we can think $s(v)$ is $k$-tuple. I called $s(v)$ spectrum of $v$.)
(3) When two vertices $v$ and $w$ are adjacent, define
$p(v, w) = (v(2)w(1)+v(3)w(2)+\cdots+v(1)w(k)) - (v(1)w(2) + v(2)w(3) + \cdots + v(k)w(1)) $ (where $v(i)$ denote $i$'th component of $s(v)$)
If $v(i-1)=0$ and $v(i+1)=1$ and $w(i)=1$ then $w(i)$ contribute $+1$ to $p(v, w)$ and if $v(i-1)=1$ and $v(i+1)=0$ and $w(i)=1$ then $w(i)$ contribute $-1$ to $p(v, w)$ and otherwise $w(i)$ does not contribute to $p(v, w)$. Let $w_1, w_2, \cdots , w_m$ is all vertices adjacent to $v$.
Naively, If $v(i-1)=0$ and $v(i+1)=1$, that means $w_j(i)=1$ for many $j$, so many $+1$ are contributed to $p(v, w)$. In contrast, If $v(i-1)=1$ and $v(i+1)=0$, that means $w_j(i)=1$ for little $j$, so small $-1$ are contributed to $p(v, w)$. Therefore we can expect that $\sum_{j=1}^{m} p(v, w_j)$ is maybe positive.
(4) In fact, we can show that
[a] $\sum_{j=1}^{m} p(v, w_j)= 0$ (if $s(v)$ has period 1 or 2)
[b] $\sum_{j=1}^{m} p(v, w_j) > 0$ (if $s(v)$ has period larger than 2)
[c] $p(v, w) + p(w, v) = 0$
So summation of $p(v, w)$ about all two possible adjacent vertex $v, w$ must be 0 (by [c]). But if there is vertex $v$ that s(v) has period larger than 2, its value must be positive (by [a], [b]).
Sorry for poor English and unfriendly explain.
Unfortunately, I don’t found the respective talk at the conferences pages (but there still is an option to ask about my colleague who attended the same conferences). Nevertheless, I googled two relevant links, and there should be more of them.
The links which I found:
“On the Voting Time of the Deterministic Majority Process” by Dominik Kaaser, Frederik Mallmann-Trenn, and Emanuele Natale. In particular, it seems that your conjecture is true (see the abstract and the beginning of page 4).
Section 1.3 "Related work" of the book “Language, Culture, Computation” by eds. Nachum Dershowitz and Ephraim Nissan should contain some relevant references.