Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

On the period-two-property of the majority operator in infinite graphs


Author: Gadi Moran
Journal: Trans. Amer. Math. Soc. 347 (1995), 1649-1667
MSC: Primary 68R10; Secondary 68Q80, 68Q90, 90C35
DOI: https://doi.org/10.1090/S0002-9947-1995-1297535-1
MathSciNet review: 1297535
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 68R10, 68Q80, 68Q90, 90C35

Retrieve articles in all journals with MSC: 68R10, 68Q80, 68Q90, 90C35


Additional Information

Keywords: Period-two, majority rule, cellular automata, infinite graphs
Article copyright: © Copyright 1995 American Mathematical Society