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
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

DOI: https://doi.org/10.1090/S0002-9947-1995-1297535-1
Keywords: Period-two, majority rule, cellular automata, infinite graphs
Article copyright: © Copyright 1995 American Mathematical Society