Reachability and recurrence in a modular generalization of annihilating random walks (and Lights-Out games) to hypergraphs

DOI10.1016/J.TCS.2015.02.035MaRDI QIDQ2344774zbMATH OpenOpenAlexFDO

Authors Gabriel Istrate

Publication date 18 May 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.1440

zbMATH Keywords

discrete complex systemsLights-Out gamesreachability

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65) Random walks on graphs (05C81) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Games involving graphs (91A43)

Abstract: We study a dynamical system motivated by our earlier work on the statistical physics of social balance on graphs that can be viewed as a generalization of annihilating walks along two directions: first, the interaction topology is a hypergraph; second, the ``number of particles`` at a vertex of the hypergraph is an element of a finite field $$ of integers modulo $p$, $pgeq3$. Equivalently, particles move on a hypergraph, with a moving particle at a vertex being replaced by one indistinguishable copy at each neighbor in a given hyperedge; particles at a vertex collectively annihilate when their number reaches $p$. The system we study can also be regarded as a natural generalization of certain lights-out games to finite fields and hypergraph topologies. Our result shows that under a liberal sufficient condition on the nature of the interaction hypergraph there exists a polynomial time algorithm (based on linear algebra over $$) for deciding reachability and recurrence of this dynamical system. Interestingly, we provide a counterexample that shows that this connection does not extend to all graphs.

Recommendations

• scientific article; zbMATH DE number 2046069
• \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
• Computer Aided Verification
• Generalized loop-erased random walks and approximate reachability
• Zero-sum dynamic games and a stochastic variation of Ramsey's theorem
• scientific article; zbMATH DE number 3970795
• High-order random walks and generalized Laplacians on hypergraphs
• scientific article; zbMATH DE number 777287
• High-ordered random walks and generalized Laplacians on hypergraphs

Cites work

• A Random Recolouring Method for Graphs and Hypergraphs
• A randomised 3-colouring algorithm
• A survey on the use of Markov chains to randomly sample colourings
• Additive and cancellative interacting particle systems
• Asymptotic density in a threshold coalescing and annihilating random walk
• Computational mechanics of cellular automata: an example
• Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?
• Finite particle systems and infection models
• Flux and fixation in cyclic particle systems
• Graphs whose neighborhoods have no special cycles
• scientific article; zbMATH DE number 3928066 (Why is no real title available?)
• scientific article; zbMATH DE number 4026522 (Why is no real title available?)
• scientific article; zbMATH DE number 2125071 (Why is no real title available?)
• Hypergraph Coloring Games and Voter Models
• Linear cellular automata and the garden-of-eden
• On a modular domination game.
• On the Dynamics of Social Balance on General Networks (with an application to XOR-SAT)
• Random Lights Out processes on graphs
• Random Seidel switching on graphs
• Reliable cellular automata with self-organization
• Social balance on networks: the dynamics of friendship and enmity
• Stochastic dynamics on hypergraphs and the spatial majority rule model
• Structure and importance of logspace-MOD class

This page was built for publication: Reachability and recurrence in a modular generalization of annihilating random walks (and Lights-Out games) to hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344774)