Local-to-Global Principles for the Hitting Sequence of a Rotor Walk
In rotor walk on a finite directed graph, the exits from each vertex follow a prescribed periodic sequence. Here we consider the case of rotor walk where a particle starts from a designated source vertex and continues until it hits a designated target set, at which point the walk is restarted from t...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Electronic Journal of Combinatorics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/89789 |
| _version_ | 1826215377332338688 |
|---|---|
| author | Giacaglia, Giuliano Pezzolo Levine, Lionel Propp, James Zayas-Palmer, Linda |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Giacaglia, Giuliano Pezzolo Levine, Lionel Propp, James Zayas-Palmer, Linda |
| author_sort | Giacaglia, Giuliano Pezzolo |
| collection | MIT |
| description | In rotor walk on a finite directed graph, the exits from each vertex follow a prescribed periodic sequence. Here we consider the case of rotor walk where a particle starts from a designated source vertex and continues until it hits a designated target set, at which point the walk is restarted from the source. We show that the sequence of successively hit targets, which is easily seen to be eventually periodic, is in fact periodic. We show moreover that reversing the periodic patterns of all rotor sequences causes the periodic pattern of the hitting sequence to be reversed as well. The proofs involve a new notion of equivalence of rotor configurations, and an extension of rotor walk incorporating time-reversed particles. |
| first_indexed | 2024-09-23T16:26:23Z |
| format | Article |
| id | mit-1721.1/89789 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:26:23Z |
| publishDate | 2014 |
| publisher | Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | mit-1721.1/897892022-10-02T07:59:17Z Local-to-Global Principles for the Hitting Sequence of a Rotor Walk Giacaglia, Giuliano Pezzolo Levine, Lionel Propp, James Zayas-Palmer, Linda Massachusetts Institute of Technology. Department of Mathematics Giacaglia, Giuliano Pezzolo Zayas-Palmer, Linda In rotor walk on a finite directed graph, the exits from each vertex follow a prescribed periodic sequence. Here we consider the case of rotor walk where a particle starts from a designated source vertex and continues until it hits a designated target set, at which point the walk is restarted from the source. We show that the sequence of successively hit targets, which is easily seen to be eventually periodic, is in fact periodic. We show moreover that reversing the periodic patterns of all rotor sequences causes the periodic pattern of the hitting sequence to be reversed as well. The proofs involve a new notion of equivalence of rotor configurations, and an extension of rotor walk incorporating time-reversed particles. Massachusetts Institute of Technology. Undergraduate Research Opportunities Program National Science Foundation (U.S.) (Grant 0644877) National Science Foundation (U.S.) (Grant 1001905) National Science Foundation (U.S.) (Postdoctoral Research Fellowship) National Science Foundation (U.S.). Research Experience for Undergraduates (Program) 2014-09-17T12:53:03Z 2014-09-17T12:53:03Z 2012-01 2011-08 Article http://purl.org/eprint/type/JournalArticle 1077-8926 http://hdl.handle.net/1721.1/89789 Giacaglia, Giuliano Pezzolo, Lionel Levine, James Propp, and Linda Zayas-Palmer. "Local-to-Global Principles for the Hitting Sequence of a Rotor Walk." Electronic Journal of Combinatorics, Volume 19, Issue 1 (2012). en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p5 Electronic Journal of Combinatorics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Electronic Journal of Combinatorics Electronic Journal of Combinatorics |
| spellingShingle | Giacaglia, Giuliano Pezzolo Levine, Lionel Propp, James Zayas-Palmer, Linda Local-to-Global Principles for the Hitting Sequence of a Rotor Walk |
| title | Local-to-Global Principles for the Hitting Sequence of a Rotor Walk |
| title_full | Local-to-Global Principles for the Hitting Sequence of a Rotor Walk |
| title_fullStr | Local-to-Global Principles for the Hitting Sequence of a Rotor Walk |
| title_full_unstemmed | Local-to-Global Principles for the Hitting Sequence of a Rotor Walk |
| title_short | Local-to-Global Principles for the Hitting Sequence of a Rotor Walk |
| title_sort | local to global principles for the hitting sequence of a rotor walk |
| url | http://hdl.handle.net/1721.1/89789 |
| work_keys_str_mv | AT giacagliagiulianopezzolo localtoglobalprinciplesforthehittingsequenceofarotorwalk AT levinelionel localtoglobalprinciplesforthehittingsequenceofarotorwalk AT proppjames localtoglobalprinciplesforthehittingsequenceofarotorwalk AT zayaspalmerlinda localtoglobalprinciplesforthehittingsequenceofarotorwalk |