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

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

  • [GFP] E. Goles, F. Fogelman-Soulie, and D. Pellegrin, Decreasing energy functions as a tool for studying threshold networks, Discrete Appl. Math. 12 (1985), 261-277. MR 813974 (87d:68084)
  • [GM] E. Goles and S. Martinez, Neural and automata networks, Kluwer Academic, Dordrecht, 1990. MR 1047470 (91h:58059)
  • [GO] E. Goles and J. Olivos, Periodic behaviour of generalized threshold functions, Discrete Math. 30 (1980), 187-189. MR 566436 (82c:68033)
  • [GOd] E. Goles and A. Odlyzko, Decreasing energy functions and the lengths of transients for some cellular automata, Complex Systems 2 (1988), 501-507. MR 971606 (90c:68052)
  • [M1] G. Moran, The $ r$-majority-vote action on 0-$ 1$ sequences, Discrete Math. 132 (1994), 145-174. MR 1297380 (95m:92001)
  • [M2] -, Parametrization for stationary patterns of the $ r$-majority operators on 0-$ 1$ sequences, Discrete Math. 132 (1994), 175-195. MR 1297381 (95m:92002)
  • [OR] A. M. Odlyzko and D. J. Randal, On the periods of some graph transformations, Complex Systems 1 (1987), 203-210. MR 891521 (88d:05161)
  • [PS] S. Poljak and M. Sura, On periodical behaviour in societies with symmetric influences, Combinatorica 3 (1983), 119-121. MR 716427 (85a:90022)
  • [PT] S. Poljak and D. Turzik, On an application of convexity to discrete systems, Discrete Appl. Math. 13 (1986), 27-32. MR 829336 (87k:58133)

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

American Mathematical Society