Reachability and recurrence in a modular generalization of annihilating random walks (and lights-out games) on hypergraphs

Details Reachability and recurrence in a modular generalization of annihilating random walks (and lights-out games) on hypergraphs Reachability and recurrence in a modular generalization of annihilating random walks (and lights-out games) on hypergraphs

2011-02-07

arxiv.org/abs/1102.1440v1

Mathematics

Combinatorics

Scientific paper

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 ${\bf Z}_{p}$ of integers modulo $p$, $p\geq 3$. 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 ${\bf Z}_{p}$) 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.

Affiliated with

Also associated with

No associations

Rating

Reachability and recurrence in a modular generalization of annihilating random walks (and lights-out games) on hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reachability and recurrence in a modular generalization of annihilating random walks (and lights-out games) on hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reachability and recurrence in a modular generalization of annihilating random walks (and lights-out games) on hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-501568