ON THE PERIOD-2-PROPERTY OF THE MAJORITY OPERATOR IN INFINITE-GRAPHS

A self-mapping M:X --> X of a nonempty set X has the Period-Two-Property (p2p) if M(2)x = x holds for every M-periodic point x is an element of X. Let X be the set of all {0, 1}-labelings x: V --> {0, 1} of the set of vertices V of a locally finite connected graph G. For x is an element of X let Mx is an element of X label v is an element of V by the majority bit that x applies to its neighbors, retaining v'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 1/n log b(n) --> 0, where b(n) is the number of v is an element of V at a distance at most n from a fixed vertex v(0) is an element of V.