Tanya Khovanova's Math Blog

Rotor-Router Networks

24th November 2011, 04:04 pm

I have two admirers, Alex and Mike. Alex lives next to my home and Mike lives next to my MIT office. I have a lousy memory, so I invented the following system to guarantee that I see both of my friends and also manage to come to my office from time to time. I have a sign hanging on the inside of my home door that says Office on one side and Alex on the other. When I approach the door, I can see right away where I went last time. So I flip the sign and that tells me where next to go. I have a similar sign inside my office door that tells me to go either to home or to Mike. Every evening I spend with one of my admirers discussing puzzles or having coffee. Late at night I come home to sleep in my own bed. Now let’s see what happens if today my home sign shows Office and the office sign shows Mike:

Today. I flip the home sign to Alex and spend the evening with Alex.
Tomorrow. I flip the home sign to Office and go to MIT. Later I flip the office sign to Home and return home. As I cannot stand to spend the evening at home alone, I go out again. I flip the home sign to Alex and spend the evening with Alex.
The day after tomorrow. I flip the home sign to Office and go there. Later I flip the office sign to Mike and spend the evening with Mike.

After three days the signs return to their original positions, meaning that the situation is periodic and I will repeat this three-day pattern forever.

Let’s get back to reality. I am neither memory-challenged nor addicted to coffee. I invented Alex and Mike to illustrate a rotor-router network. In general my home is called a source: the place where I wake up and start the day. There can only be one source in the network. My admirers are called targets and I can have an infinite number of them. The network needs to be constructed in such a way that I always end up with a friend by the end of the day. There could be many other places that I can visit, other than my office: for example, the library, the gym, opera and so on. These places are other vertices of a network that could be very elaborate. Any place where I go, there is a sign that describes a pattern of where I go from there. The sign is called a rotor.

The patterns at every rotor might be more complicated than a simple sign. Those patterns are called rotor types. My sign is called 12 rotor type as it switches between the first and the second directions at every non-friend place I visit.

The sequence of admirers that I visit is called a hitting sequence and it can be proved that the sequence is eventually periodic. Surprisingly, the stronger result is also true: the hitting sequence is purely periodic.

The simple 12 rotor is universal. That means that given a set of friends and a fancy periodic schedule that designates the order I want to visit them in, I can create a network of my activities where every place has a sign of this type 12 and where I will end up visiting my friends according to my pre-determined periodic schedule.

It is possible to see that not every rotor type is universal. For example, palindromic rotor types generate only palindromic hitting sequences, thus they are not universal. The smallest such example, is rotor type 121. Also, block-repetitive rotor types, like 1122, generate block-repetitive hitting sequences.

It is a difficult and an interesting question to describe universal rotor types. My PRIMES student Xiaoyu He was given a project, suggested by James Propp, to prove or disprove the universality of the 11122 rotor type. This was the smallest rotor type the universality of which was not known. Xiaoyu He proved that 11122 is universal and discovered many other universal rotor types. His calculations support the conjecture that only palindromic or block-repetitive types are not universal. You can find these results and many more in his paper: On the Classification of Universal Rotor-Routers.