Mathematics – Combinatorics
Scientific paper
2007-05-10
Journal of Combinatorial Theory, Series A 116(2), 421--433, 2009
Mathematics
Combinatorics
v2 incorporates referee comments, clarifies that the results of section 2 apply also to multigraphs
Scientific paper
10.1016/j.jcta.2008.05.012
The rotor-router model is a deterministic analogue of random walk. It can be used to define a deterministic growth model analogous to internal DLA. We show that the set of occupied sites for this model on an infinite regular tree is a perfect ball whenever it can be, provided the initial rotor configuration is acyclic (that is, no two neighboring vertices have rotors pointing to one another). This is proved by defining the rotor-router group of a graph, which we show is isomorphic to the sandpile group. We also address the question of recurrence and transience: We give two rotor configurations on the infinite ternary tree, one for which chips exactly alternate escaping to infinity with returning to the origin, and one for which every chip returns to the origin. Further, we characterize the possible "escape sequences" for the ternary tree, that is, binary words a_1 ... a_n for which there exists a rotor configuration so that the k-th chip escapes to infinity if and only if a_k=1.
Landau Itamar
Levine Lionel
No associations
LandOfFree
The Rotor-Router Model on Regular Trees 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 The Rotor-Router Model on Regular Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Rotor-Router Model on Regular Trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-410931