On the Period-Two-Property of the Majority Operator in Infinite Graphs
Gadi Moran · Transactions of the American Mathematical Society · 1995
A self-mapping $M:X \to X$ of a nonempty set $X$ has the Period-Two-Property (p2p) if ${M^2}x = x$ holds for every $M$-periodic point $x \in X$. Let $X$ be the set of all $\{ 0,1\}$-labelings $x:V \to \{ 0,1\}$ of the set of vertices $V$ of a locally finite connected graph $G$. For $x \in X$ let $Mx \in X$ label $v \in V$ by the majority bit that $x$ applies to its neighbors, retaining $\upsilon$’s $x$-label in case of a tie. We show that $M$ has the p2p if there is a finite bound on the degrees in $G$ and $\frac {1} {n}\log {b_n} \to 0$, where ${b_n}$ is the number of $\upsilon \in V$ at a distance at most $n$ from a fixed vertex ${\upsilon _0} \in V$.