\documentclass[12pt]{article} \usepackage{e-jc} \specs{P30}{19(3)}{2012} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{aecompl} \usepackage{ae} \usepackage{textcomp} %\usepackage[english]{babel} %\usepackage{pdfsync} \usepackage{tikz} \usetikzlibrary{arrows,automata} \usetikzlibrary{positioning} \usepackage{pgffor} \usepackage{dsfont} \usepackage{capt-of} \usepackage{amssymb} \usepackage{varwidth} \usepackage{multirow} \usepackage{rotating} \usepackage{booktabs} \usepackage{subfig} \usepackage[leftcaption]{sidecap} \usepackage{caption} \usepackage{hyperref} \usepackage{hypbmsec} \usepackage{amsmath,amsthm,amsfonts} \usepackage{mathtools} \usepackage{bbm} \usepackage{enumerate} \theoremstyle{plain} \newtheorem{thm}{Theorem}[section] \newtheorem{prop}[thm]{Proposition} \newtheorem{cor}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{rem}[thm]{Remark} \newtheorem{defn}[thm]{Definition} \theoremstyle{definition} \newtheorem{exam}[thm]{Example} \newcommand{\e}{\mathrm{e}} \newcommand{\E}{\mathbb{E}} \renewcommand{\P}{\mathbb{P}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\D}{\mathcal{D}} \newcommand{\T}{\mathcal{T}} \newcommand{\wiredT}[1][h]{\widetilde{\mathcal{T}}^{#1}} \usepackage{cmll} \newcommand{\up}{\shneg} \newcommand{\down}{\shpos} \newcommand{\G}{\mathsf{G}} \renewcommand{\H}{\mathsf{H}} \renewcommand{\O}{\mathcal{O}} \renewcommand{\d}{\mathrm{d}} \newcommand{\shell}[1]{\mathcal{S}_{#1}} \newcommand{\ball}[1]{\mathcal{B}_{#1}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\indicator}[1]{\mathds{1}_{#1}} \renewcommand{\labelenumi}{\upshape(\alph{enumi})} \renewcommand{\theenumi}{(\alph{enumi})} \newcommand{\rad}{\operatorname{rad}} \newcommand{\Var}{\operatorname{Var}} \newcommand{\supp}{\operatorname{supp}} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\rec}{\mathsf{Rec}} \newcommand{\rr}{\mathsf{RR}} \newcommand{\sand}{\mathsf{SP}} \renewcommand{\r}{\mathsf{r}} \newcommand{\todo}[1]{\textcolor{red}{#1}} \newcommand{\fdefeq}{\overset{\text{def.}}{=}} \newcommand{\p}{\dfrac{\partial}{\partial z}} \newcommand{\pp}{\dfrac{\partial^2}{\partial z^2}} \newcommand{\pr}[1]{\dfrac{\partial^{#1}}{\partial z^{#1}}} \newenvironment{eqsystem}% {\left[ \begin{aligned}}% {\end{aligned} \right.} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \hypersetup{% pdftitle = {The rotor-router group of directed covers of graphs}, pdfauthor = {Wilfried Huss, Ecaterina Sava}, pdfkeywords = {rotor-router walks, rotor-router group, sandpile group, directed cover} } \title{The rotor-router group of directed covers of graphs} \author{Wilfried Huss\\ \small Institute of Discrete Mathematics\\[-0.8ex] \small Vienna University of Technology\\[-0.8ex] \small Wiedner Hauptstrasse 8-10\\[-0.8ex] \small 1040 Vienna, Austria\\ \small \texttt{wilfried.huss@tuwien.ac.at} \and Ecaterina Sava\\ \small Department of Mathematics C\\[-0.8ex] \small Graz University of Technology\\[-0.8ex] \small Steyrergasse 30/III\\[-0.8ex] \small 8010 Graz, Austria\\ \small \texttt{sava@tugraz.at} } \date{\dateline{Jun 19, 2012}{Aug 23, 2012}{Sep 6, 2012}\\ \small Mathematics Subject Classifications: 05C05; 05C25; 82C20} \begin{document} \maketitle \begin{abstract} A rotor-router walk is a deterministic version of a random walk, in which the walker is routed to each of the neighbouring vertices in some fixed cyclic order. We consider here directed covers of graphs (called also periodic trees) and we study several quantities related to rotor-router walks on directed covers. The quantities under consideration are: order of the rotor-router group, order of the root element in the rotor-router group and the connection with random walks. \bigskip\noindent \textbf{Keywords:} finite graphs, directed covers, periodic trees, rotor-router walks, rotor-router group, sandpile group. \end{abstract} %============================================================================= \section{Introduction} Given a finite connected and directed graph $\G$, one can construct, for each vertex $i\in\G$, a labelled undirected rooted tree $\T_i$ in the following way. The root vertex of $\T_i$ is labelled with $i$. Recursively if $x$ is a vertex of $\T_j$ with label $j\in\G$, then for each $k\in \G$ the vertex $x$ has $d_{jk}$ successors with label $k$, where $D=(d_{jk})$ is the adjacency matrix of $\G$. The tree $\T_i$ is called the \emph{directed cover} of $\G$ with root of type $i$. Random walks on directed covers of graphs have been studied by \textsc{Takacs} \cite{Takacs97randomwalk}, \textsc{Nagnibeda and Woess} \cite{woess_nagnibeda}. \emph{Rotor-router walks} are deterministic analogues to random walks, which have been first introduced into the physics literature under the name \emph{Eulerian walks} by \textsc{Priezzhev, D.Dhar et al} \cite{PhysRevLett.77.5079} as a model of \emph{self organized criticality}. In a rotor-router walk on a graph, equip each vertex with an arrow (the rotor) pointing to one of the neighbours of the vertex. A particle performing a rotor-router walk carries out the following procedure at each step. First it changes the rotor at its current position to point to the next neighbour, in a fixed order chosen at the beginning, and then moves to the neighbour the rotor is now pointing at. These deterministic walks have gained increased interest in the last years, and in many settings there is remarkable agreement between the behaviour of rotor-router walks and the expected behaviour of random walks. \textsc{Holroyd and Propp} \cite{holroyd_propp} proved that many quantities associated to rotor-router walks such as normalized hitting frequencies, hitting times and occupation frequencies, are concentrated around their expected values for random walks. See also {\sc Cooper and Spencer} \cite{cooper_spencer_2006}, {\sc Doerr and Friedrich} \cite{doerr_friedrich_2007}, {\sc Angel and Holroyd} \cite{angel_holroyd_2011}, {\sc Kleber} \cite{kleber_goldbug}, and also \textsc{Cooper, Doerr et al.} \cite{cooper_doerr_friedrich_spencer_2006}. On the other hand, rotor-router walks and random walks can also have striking differences. In questions concerning recurrence and transience of rotor-router walks on homogeneous trees, this has been proven by {\sc Landau and Levine} \cite{landau_levine_2009}. For random initial configurations on homogeneous trees, see {\sc Angel and Holroyd} \cite{angel_holroyd_2011}. In our note \cite{huss_sava_transience_dircovers} we have extended their result to rotor-router walks on directed covers of finite graphs. Furthermore, one can use rotor-router walks for solving questions regarding the behaviour of random walks: for instance, in \cite{huss_sava_rotor} we have used a special rotor-router process in order to determine the harmonic measure, that is, the exit distribution of a random walk from a finite subset of a graph. In this work, we continue the study of several quantities related to rotor-router walks such as the order of the rotor-router group and the order of the root element in the rotor group on directed covers of finite graphs. On homogeneous trees, this was done by \textsc{Levine}\cite{levine_sandpile_tree}. The remainder of the paper is structured as follows. In Section \ref{sec:preliminaries} we briefly review the definitions and basic properties of: graphs and trees, directed covers of graphs, rotor-router walks, rotor-router and sandpile groups and the connection between them. We will follow the notation from \cite{huss_sava_transience_dircovers}. Section \ref{sec:order_rr_group} is dedicated to the study of the rotor-router group on finite pieces of directed covers $\T_i$ of finite graphs $\G$, with $i\in\G$. In particular we study the rotor-router group on balls with respect to the graph metric, that is on $\T^h_i = \{x\in\T_i: \d(r,x) \leq h\}$, where $r$ is the root vertex of the graph and $\d(r,x)$ is the length of the shortest path from $r$ to $x$. To the graph $\T^h_i$ we add a global sink vertex, which is connected to the root and all leaves. By counting a certain family of rooted spanning forests, we give a recurrence formula in Theorem \ref{thm:recurent_rotor_group} for the order of the rotor-router group on directed covers $\T^h_i$ in terms of the respective orders on the principal subbranches of $\T^h_i$. Furthermore, in Theorem \ref{thm:asymptotics_rrorder} we show that the order grows doubly exponential in $h$. The growth depends on the spectral radius of the adjacency matrix of $\G$. Then, we consider the order of the root element in the rotor-router group, which can be defined as the number of particles needed at the origin of $\T^h_i$, such that after performing a rotor-router walk and stopping the particles when they hit the sink, we are back to the same rotor-router configuration we started from. We describe in Theorem \ref{thm:root_element_order} a recursive way for finding the order of the root element in terms of the respective orders of the subbranches. A key tool in the proof of this result is the so-called \emph{explosion formula} introduced by {\sc Angel and Holroyd} \cite{angel_holroyd_2011}. \section{Preliminaries}\label{sec:preliminaries} \paragraph{Graphs and Trees.} Let $\G=(V,E)$ be a locally finite and connected directed multigraph, with vertex set $V$ and edge set $E$. For sake of simplicity, we identify the graph $\G$ with its vertex set $V$, i.e., $i\in \G$ means $i\in V$. It will be clear from the context whether we are speaking about vertices or edges. If $(i,j)$ is an edge of $\G$, we write $i\sim_{\G}j$. We write $\d(i,j)$ for the {\em graph distance}, that is, the length of the shortest path between $i$ and $j$. A directed graph $\G$ is {\em strongly connected} if for every two vertices $i$ and $j$ there exists a directed path from $i$ to $j$ and a directed path from $j$ to $i$. Let $D=(d_{ij})_{i,j\in\G}$ be the \emph{adjacency matrix} of $\G$, where $d_{ij}$ is the number of directed edges connecting $i$ to $j$. We write $d_i$ for the sum of the entries in the $i$-th row of $D$, that is $d_{i}=\sum_{j\in\G} d_{ij}$ is the {\em degree} of the vertex $i$ (or the number of the outgoing edges from $i$). The adjacency matrix $D$ is {\em irreducible} if for every pair of indices $i$ and $j$ there exists a natural number $n$ such that $d^{(n)}_{ij}>0$, where $d^{(n)}_{ij}$ represents the $(i,j)$-entry of the matrix power $D^n$. If $\G$ is strongly connected, its adjacency matrix is irreducible. A {\em tree} $\T$ is a connected, cycle-free graph. A {\em rooted tree} is a tree with a distinguished vertex $r$, called {\em the root}. For a vertex $x\in\T$, denote by $|x|$ the {\em height} of $x$, that is the graph distance from the root to $x$. For any positive integer $h$, define the {\em truncated tree} $\T^h = \{x\in\T: |x| \leq h\}$ to be the subgraph of $\T$ induced by the vertices at height smaller or equal to $h$. For a vertex $x\in \T\setminus\{r\}$, denote by $x^{(0)}$ its {\em ancestor}, that is the unique neighbour of $x$ closer to the root $r$. It will be convenient to attach an additional vertex $r^{(0)}$ to the root $r$, which will be considered in the following as a sink vertex. Additionally we fix a planar embedding of $\T$ and enumerate the neighbours of a vertex $x\in \T$ in counter-clockwise order $\big(x^{(0)}, x^{(1)}, \ldots, x^{(d_x-1)}\big)$ beginning with the ancestor. We will call a vertex $y$ a \emph{descendant} of $x$, if $x$ lies on the unique shortest path from $y$ to the root $r$. A descendant of $x$, which is also a neighbour of $x$, will be called a \emph{child}. A \emph{cone} $C_x$ rooted a $x$ is the subtree spanned by the descendants of $x$. The {\em principal branches} of $\T$ are the cones rooted at the children of the root $r$. The \emph{wired tree} $\wiredT$ of height $h$ is the multigraph obtained from $\T^h$ by collapsing all leaves, i.e. all vertices $y\in \T$ with $\d(r,y) = h$, together with the ancestor $r^{(0)}$ of the root to a single vertex $s$, the sink. We do not collapse multiple edges. %============================================================================= \paragraph{Directed Covers of Graphs.} Let now $\G$ be a finite, directed and strongly connected multigraph with adjacency matrix $D=(d_{ij})$. Let $m$ be the cardinality of the vertices of $\G$, and label the vertices of $\G$ by $\{1,2,\ldots, m \}$. For $i\in\G$, the {\em directed cover} $\T_i$ of $\G$ is defined recursively as an undirected rooted tree whose vertices are labelled by the vertex set $\{1,2,\ldots, m \}$ of $\G$. The root $r$ of $\T_i$ is labelled with $i\in\G$. Recursively, if $x$ is a vertex in $\T_i$ with label $j\in \G$, then $x$ has $d_{jk}$ descendants with label $k$, for each $k\in\G$. We define the {\em label function} $\tau:\T_i\to\G$ as the map that associates to each vertex in $\T_i$ its label in $\G$. The label $\tau(x)$ of a vertex $x$ will be also called the {\em type} of $x$. For a vertex $x\in\T_i$, we will not only need its type, but also the types of its children. In order to keep track of the type of a vertex and the types of its children we introduce the {\em generation function} $\chi = \left(\chi_i\right)_{i\in\G}$ with $\chi_i:\{1,\ldots,d_i\}\to\G$. For a vertex $x$ of type $i$, $\chi_i(k)$ represents the type of the $k$-th child $x^{(k)}$ of $x$, i.e., \begin{equation*} \text{if } \tau(x)=i \text{ then } \chi_i(k)=\tau(x^{(k)}), \text{ for } k=1,\ldots,d_i. \end{equation*} As the neighbours $\big(x^{(0)},\ldots, x^{(d_{\tau(x)})}\big)$ of any vertex $x$ are drawn in clockwise order, the generation function $\chi$ also fixes the planar embedding of the tree and thus defines $\T_i$ uniquely as a planted plane tree. In order to distinguish between the two graphs $\G$ and $\T_i$ we use the variables $i,j$ for vertices in $\G$ (and labels or types in $\T$) and $x,y$ for vertices of $\T$. The tree $\mathcal{T}_i$ constructed in this way is called the \emph{directed cover} of $\G$ with root of type $i$. Note that, for each $i\in\G$, the directed cover $\T_i$ of $\G$ is an undirected tree. Such trees are also known as \emph{periodic trees}, see {\sc Lyons} \cite{LP:book}, or \emph{trees with finitely many cone types} in {\sc Nagnibeda and Woess} \cite{woess_nagnibeda}. We say that the cone $C_x$ has {\em cone type} $\tau(x)$. Note that if $x,y\in\T_i$ have the same label, that is $\tau(x)=\tau(y)$, then the trees $C_x$ and $C_y$ are isomorphic as rooted trees. Since $\G$ is a finite graph, the number of isomorphism classes of $C_x$, $x\in\T_i$ is finite. The graph $\G$ is called the \emph{base graph} or the \emph{generating graph} for the tree $\T_i$. In the following we give two basic examples of directed covers of graphs. \begin{figure} \centering \begin{tikzpicture}[scale=0.65] \begin{scope}[xshift=-3cm, yshift=1cm] \node (chi) at (0,0) { \begin{tabular}{lc|cc} \multicolumn{2}{c}{} & \multicolumn{2}{l}{\scalebox{0.7}{$k\rightarrow$}} \\ \multicolumn{2}{c|}{$\chi_i(k)$} & 1 & 2 \\ \hline \multirow{2}{*}{\scalebox{0.7}{\rotatebox{-90}{\rotatebox{90}{$i$} $\rightarrow$}}} & 1 & 2 & \\ & 2 & 2 & 1 \end{tabular} }; \end{scope} \begin{scope}[xscale=0.8] \coordinate (n0) at (4.65625,0); \coordinate (n1) at (4.65625,1); \coordinate (n3) at (1.625,2); \coordinate (n22) at (1.625,3); \coordinate (n24) at (0.5,4); \coordinate (n30) at (0.5,5); \coordinate (n32) at (0,6); \coordinate (n31) at (1,6); \coordinate (n23) at (2.75,4); \coordinate (n26) at (2.0,5); \coordinate (n29) at (2,6); \coordinate (n25) at (3.5,5); \coordinate (n28) at (3,6); \coordinate (n27) at (4,6); \coordinate (n2) at (7.6875,2); \coordinate (n5) at (5.75,3); \coordinate (n16) at (5.75,4); \coordinate (n18) at (5.0,5); \coordinate (n21) at (5,6); \coordinate (n17) at (6.5,5); \coordinate (n20) at (6,6); \coordinate (n19) at (7,6); \coordinate (n4) at (9.625,3); \coordinate (n7) at (8.5,4); \coordinate (n13) at (8.5,5); \coordinate (n15) at (8,6); \coordinate (n14) at (9,6); \coordinate (n6) at (10.75,4); \coordinate (n9) at (10.0,5); \coordinate (n12) at (10,6); \coordinate (n8) at (11.5,5); \coordinate (n11) at (11,6); \coordinate (n10) at (12,6); \end{scope} \draw (n1) -- (n0); \draw (n3) -- (n1); \draw (n22) -- (n3); \draw (n24) -- (n22); \draw (n30) -- (n24); \draw (n32) -- (n30); \draw (n31) -- (n30); \draw (n23) -- (n22); \draw (n26) -- (n23); \draw (n29) -- (n26); \draw (n25) -- (n23); \draw (n28) -- (n25); \draw (n27) -- (n25); \draw (n2) -- (n1); \draw (n5) -- (n2); \draw (n16) -- (n5); \draw (n18) -- (n16); \draw (n21) -- (n18); \draw (n17) -- (n16); \draw (n20) -- (n17); \draw (n19) -- (n17); \draw (n4) -- (n2); \draw (n7) -- (n4); \draw (n13) -- (n7); \draw (n15) -- (n13); \draw (n14) -- (n13); \draw (n6) -- (n4); \draw (n9) -- (n6); \draw (n12) -- (n9); \draw (n8) -- (n6); \draw (n11) -- (n8); \draw (n10) -- (n8); \fill[black] (n0) circle (2pt); \fill[red] (n1) circle (2pt); \fill[blue] (n3) circle (2pt); \fill[red] (n22) circle (2pt); \fill[blue] (n24) circle (2pt); \fill[red] (n30) circle (2pt); \fill[black] (n32) circle (2pt); \fill[black] (n31) circle (2pt); \fill[red] (n23) circle (2pt); \fill[blue] (n26) circle (2pt); \fill[black] (n29) circle (2pt); \fill[red] (n25) circle (2pt); \fill[black] (n28) circle (2pt); \fill[black] (n27) circle (2pt); \fill[red] (n2) circle (2pt); \fill[blue] (n5) circle (2pt); \fill[red] (n16) circle (2pt); \fill[blue] (n18) circle (2pt); \fill[black] (n21) circle (2pt); \fill[red] (n17) circle (2pt); \fill[black] (n20) circle (2pt); \fill[black] (n19) circle (2pt); \fill[red] (n4) circle (2pt); \fill[blue] (n7) circle (2pt); \fill[red] (n13) circle (2pt); \fill[black] (n15) circle (2pt); \fill[black] (n14) circle (2pt); \fill[red] (n6) circle (2pt); \fill[blue] (n9) circle (2pt); \fill[black] (n12) circle (2pt); \fill[red] (n8) circle (2pt); \fill[black] (n11) circle (2pt); \fill[black] (n10) circle (2pt); \draw[dashed] (n10) -- (n32); \node (sup) [right=0.125 of n10] {$s^\up$}; \node (sdown) [right=0.125 of n0] {$s_\down$}; \node (r) [right=0.125 of n1, yshift=-2] {$r$}; \end{tikzpicture} \caption{\label{fig:fib_tree}The wired Fibonacci tree $\wiredT[5]_2$ of height $5$ and root of type $2$.} \end{figure} \begin{exam}[{\bf Fibonacci tree}] The Fibonacci tree is the directed cover of the graph $\G$ on two vertices $\{1,2\}$, with adjacency matrix %\begin{small} \begin{equation*} D= \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \end{equation*} %\end{small} It is a tree with two cone types: a vertex with label $1$ (of type $1$) in the tree has only one child with label $2$ and a vertex of type $2$ has one child of type $1$ and one child of type $2$. In Figure \ref{fig:fib_tree} we have a wired Fibonacci tree with root type $2$ (the vertices of type $1$ are coloured in blue and those of type $2$ in red). The generation function $\chi$ is also given in the picture above. \end{exam} \begin{exam}[{\bf Bi-regular tree $\T$}] The bi-regular tree $\T$ with parameters $\alpha,\beta\in\N$ is the directed cover of the graph $\G$ on two vertices $\{1,2\}$, with adjacency matrix %\begin{small} \begin{equation*} D= \begin{pmatrix} 0 & \alpha \\ \beta & 0 \end{pmatrix} \end{equation*} %\end{small} It is a tree with two cone types: every vertex in $\T$ with label $1$ has no child with label $1$ and $\alpha=d_{12}$ children with label $2$, and every vertex with label $2$ has $\beta=d_{21}$ children with label $1$ and no child with label $2$. Since in this case, on each level there are vertices of only one type, the function $\chi$ has to be: $\chi_1(k)=2$, for $k=1,\ldots,\alpha$ and $\chi_2(k)=1$ for $k=1,\ldots,\beta$. \end{exam} \begin{figure} \centering \begin{tikzpicture}[scale=0.65] \begin{scope}[xscale=0.2] \coordinate (n0) at (35.5,0); \coordinate (n1) at (35.5,1); \coordinate (n3) at (17.5,2); \coordinate (n69) at (5.5,3); \coordinate (n111) at (2.5,4); \coordinate (n123) at (0.5,5); \coordinate (n129) at (0,6); \coordinate (n128) at (1,6); \coordinate (n122) at (2.5,5); \coordinate (n127) at (2,6); \coordinate (n126) at (3,6); \coordinate (n121) at (4.5,5); \coordinate (n125) at (4,6); \coordinate (n124) at (5,6); \coordinate (n110) at (8.5,4); \coordinate (n114) at (6.5,5); \coordinate (n120) at (6,6); \coordinate (n119) at (7,6); \coordinate (n113) at (8.5,5); \coordinate (n118) at (8,6); \coordinate (n117) at (9,6); \coordinate (n112) at (10.5,5); \coordinate (n116) at (10,6); \coordinate (n115) at (11,6); \coordinate (n68) at (17.5,3); \coordinate (n91) at (14.5,4); \coordinate (n103) at (12.5,5); \coordinate (n109) at (12,6); \coordinate (n108) at (13,6); \coordinate (n102) at (14.5,5); \coordinate (n107) at (14,6); \coordinate (n106) at (15,6); \coordinate (n101) at (16.5,5); \coordinate (n105) at (16,6); \coordinate (n104) at (17,6); \coordinate (n90) at (20.5,4); \coordinate (n94) at (18.5,5); \coordinate (n100) at (18,6); \coordinate (n99) at (19,6); \coordinate (n93) at (20.5,5); \coordinate (n98) at (20,6); \coordinate (n97) at (21,6); \coordinate (n92) at (22.5,5); \coordinate (n96) at (22,6); \coordinate (n95) at (23,6); \coordinate (n67) at (29.5,3); \coordinate (n71) at (26.5,4); \coordinate (n83) at (24.5,5); \coordinate (n89) at (24,6); \coordinate (n88) at (25,6); \coordinate (n82) at (26.5,5); \coordinate (n87) at (26,6); \coordinate (n86) at (27,6); \coordinate (n81) at (28.5,5); \coordinate (n85) at (28,6); \coordinate (n84) at (29,6); \coordinate (n70) at (32.5,4); \coordinate (n74) at (30.5,5); \coordinate (n80) at (30,6); \coordinate (n79) at (31,6); \coordinate (n73) at (32.5,5); \coordinate (n78) at (32,6); \coordinate (n77) at (33,6); \coordinate (n72) at (34.5,5); \coordinate (n76) at (34,6); \coordinate (n75) at (35,6); \coordinate (n2) at (53.5,2); \coordinate (n6) at (41.5,3); \coordinate (n48) at (38.5,4); \coordinate (n60) at (36.5,5); \coordinate (n66) at (36,6); \coordinate (n65) at (37,6); \coordinate (n59) at (38.5,5); \coordinate (n64) at (38,6); \coordinate (n63) at (39,6); \coordinate (n58) at (40.5,5); \coordinate (n62) at (40,6); \coordinate (n61) at (41,6); \coordinate (n47) at (44.5,4); \coordinate (n51) at (42.5,5); \coordinate (n57) at (42,6); \coordinate (n56) at (43,6); \coordinate (n50) at (44.5,5); \coordinate (n55) at (44,6); \coordinate (n54) at (45,6); \coordinate (n49) at (46.5,5); \coordinate (n53) at (46,6); \coordinate (n52) at (47,6); \coordinate (n5) at (53.5,3); \coordinate (n28) at (50.5,4); \coordinate (n40) at (48.5,5); \coordinate (n46) at (48,6); \coordinate (n45) at (49,6); \coordinate (n39) at (50.5,5); \coordinate (n44) at (50,6); \coordinate (n43) at (51,6); \coordinate (n38) at (52.5,5); \coordinate (n42) at (52,6); \coordinate (n41) at (53,6); \coordinate (n27) at (56.5,4); \coordinate (n31) at (54.5,5); \coordinate (n37) at (54,6); \coordinate (n36) at (55,6); \coordinate (n30) at (56.5,5); \coordinate (n35) at (56,6); \coordinate (n34) at (57,6); \coordinate (n29) at (58.5,5); \coordinate (n33) at (58,6); \coordinate (n32) at (59,6); \coordinate (n4) at (65.5,3); \coordinate (n8) at (62.5,4); \coordinate (n20) at (60.5,5); \coordinate (n26) at (60,6); \coordinate (n25) at (61,6); \coordinate (n19) at (62.5,5); \coordinate (n24) at (62,6); \coordinate (n23) at (63,6); \coordinate (n18) at (64.5,5); \coordinate (n22) at (64,6); \coordinate (n21) at (65,6); \coordinate (n7) at (68.5,4); \coordinate (n11) at (66.5,5); \coordinate (n17) at (66,6); \coordinate (n16) at (67,6); \coordinate (n10) at (68.5,5); \coordinate (n15) at (68,6); \coordinate (n14) at (69,6); \coordinate (n9) at (70.5,5); \coordinate (n13) at (70,6); \coordinate (n12) at (71,6); \end{scope} \draw (n1) -- (n0); \draw (n3) -- (n1); \draw (n69) -- (n3); \draw (n111) -- (n69); \draw (n123) -- (n111); \draw (n129) -- (n123); \draw (n128) -- (n123); \draw (n122) -- (n111); \draw (n127) -- (n122); \draw (n126) -- (n122); \draw (n121) -- (n111); \draw (n125) -- (n121); \draw (n124) -- (n121); \draw (n110) -- (n69); \draw (n114) -- (n110); \draw (n120) -- (n114); \draw (n119) -- (n114); \draw (n113) -- (n110); \draw (n118) -- (n113); \draw (n117) -- (n113); \draw (n112) -- (n110); \draw (n116) -- (n112); \draw (n115) -- (n112); \draw (n68) -- (n3); \draw (n91) -- (n68); \draw (n103) -- (n91); \draw (n109) -- (n103); \draw (n108) -- (n103); \draw (n102) -- (n91); \draw (n107) -- (n102); \draw (n106) -- (n102); \draw (n101) -- (n91); \draw (n105) -- (n101); \draw (n104) -- (n101); \draw (n90) -- (n68); \draw (n94) -- (n90); \draw (n100) -- (n94); \draw (n99) -- (n94); \draw (n93) -- (n90); \draw (n98) -- (n93); \draw (n97) -- (n93); \draw (n92) -- (n90); \draw (n96) -- (n92); \draw (n95) -- (n92); \draw (n67) -- (n3); \draw (n71) -- (n67); \draw (n83) -- (n71); \draw (n89) -- (n83); \draw (n88) -- (n83); \draw (n82) -- (n71); \draw (n87) -- (n82); \draw (n86) -- (n82); \draw (n81) -- (n71); \draw (n85) -- (n81); \draw (n84) -- (n81); \draw (n70) -- (n67); \draw (n74) -- (n70); \draw (n80) -- (n74); \draw (n79) -- (n74); \draw (n73) -- (n70); \draw (n78) -- (n73); \draw (n77) -- (n73); \draw (n72) -- (n70); \draw (n76) -- (n72); \draw (n75) -- (n72); \draw (n2) -- (n1); \draw (n6) -- (n2); \draw (n48) -- (n6); \draw (n60) -- (n48); \draw (n66) -- (n60); \draw (n65) -- (n60); \draw (n59) -- (n48); \draw (n64) -- (n59); \draw (n63) -- (n59); \draw (n58) -- (n48); \draw (n62) -- (n58); \draw (n61) -- (n58); \draw (n47) -- (n6); \draw (n51) -- (n47); \draw (n57) -- (n51); \draw (n56) -- (n51); \draw (n50) -- (n47); \draw (n55) -- (n50); \draw (n54) -- (n50); \draw (n49) -- (n47); \draw (n53) -- (n49); \draw (n52) -- (n49); \draw (n5) -- (n2); \draw (n28) -- (n5); \draw (n40) -- (n28); \draw (n46) -- (n40); \draw (n45) -- (n40); \draw (n39) -- (n28); \draw (n44) -- (n39); \draw (n43) -- (n39); \draw (n38) -- (n28); \draw (n42) -- (n38); \draw (n41) -- (n38); \draw (n27) -- (n5); \draw (n31) -- (n27); \draw (n37) -- (n31); \draw (n36) -- (n31); \draw (n30) -- (n27); \draw (n35) -- (n30); \draw (n34) -- (n30); \draw (n29) -- (n27); \draw (n33) -- (n29); \draw (n32) -- (n29); \draw (n4) -- (n2); \draw (n8) -- (n4); \draw (n20) -- (n8); \draw (n26) -- (n20); \draw (n25) -- (n20); \draw (n19) -- (n8); \draw (n24) -- (n19); \draw (n23) -- (n19); \draw (n18) -- (n8); \draw (n22) -- (n18); \draw (n21) -- (n18); \draw (n7) -- (n4); \draw (n11) -- (n7); \draw (n17) -- (n11); \draw (n16) -- (n11); \draw (n10) -- (n7); \draw (n15) -- (n10); \draw (n14) -- (n10); \draw (n9) -- (n7); \draw (n13) -- (n9); \draw (n12) -- (n9); \fill[black] (n0) circle (2pt); \fill[red] (n1) circle (2pt); \fill[blue] (n3) circle (2pt); \fill[red] (n69) circle (2pt); \fill[blue] (n111) circle (2pt); \fill[red] (n123) circle (2pt); \fill[black] (n129) circle (2pt); \fill[black] (n128) circle (2pt); \fill[red] (n122) circle (2pt); \fill[black] (n127) circle (2pt); \fill[black] (n126) circle (2pt); \fill[red] (n121) circle (2pt); \fill[black] (n125) circle (2pt); \fill[black] (n124) circle (2pt); \fill[blue] (n110) circle (2pt); \fill[red] (n114) circle (2pt); \fill[black] (n120) circle (2pt); \fill[black] (n119) circle (2pt); \fill[red] (n113) circle (2pt); \fill[black] (n118) circle (2pt); \fill[black] (n117) circle (2pt); \fill[red] (n112) circle (2pt); \fill[black] (n116) circle (2pt); \fill[black] (n115) circle (2pt); \fill[red] (n68) circle (2pt); \fill[blue] (n91) circle (2pt); \fill[red] (n103) circle (2pt); \fill[black] (n109) circle (2pt); \fill[black] (n108) circle (2pt); \fill[red] (n102) circle (2pt); \fill[black] (n107) circle (2pt); \fill[black] (n106) circle (2pt); \fill[red] (n101) circle (2pt); \fill[black] (n105) circle (2pt); \fill[black] (n104) circle (2pt); \fill[blue] (n90) circle (2pt); \fill[red] (n94) circle (2pt); \fill[black] (n100) circle (2pt); \fill[black] (n99) circle (2pt); \fill[red] (n93) circle (2pt); \fill[black] (n98) circle (2pt); \fill[black] (n97) circle (2pt); \fill[red] (n92) circle (2pt); \fill[black] (n96) circle (2pt); \fill[black] (n95) circle (2pt); \fill[red] (n67) circle (2pt); \fill[blue] (n71) circle (2pt); \fill[red] (n83) circle (2pt); \fill[black] (n89) circle (2pt); \fill[black] (n88) circle (2pt); \fill[red] (n82) circle (2pt); \fill[black] (n87) circle (2pt); \fill[black] (n86) circle (2pt); \fill[red] (n81) circle (2pt); \fill[black] (n85) circle (2pt); \fill[black] (n84) circle (2pt); \fill[blue] (n70) circle (2pt); \fill[red] (n74) circle (2pt); \fill[black] (n80) circle (2pt); \fill[black] (n79) circle (2pt); \fill[red] (n73) circle (2pt); \fill[black] (n78) circle (2pt); \fill[black] (n77) circle (2pt); \fill[red] (n72) circle (2pt); \fill[black] (n76) circle (2pt); \fill[black] (n75) circle (2pt); \fill[blue] (n2) circle (2pt); \fill[red] (n6) circle (2pt); \fill[blue] (n48) circle (2pt); \fill[red] (n60) circle (2pt); \fill[black] (n66) circle (2pt); \fill[black] (n65) circle (2pt); \fill[red] (n59) circle (2pt); \fill[black] (n64) circle (2pt); \fill[black] (n63) circle (2pt); \fill[red] (n58) circle (2pt); \fill[black] (n62) circle (2pt); \fill[black] (n61) circle (2pt); \fill[blue] (n47) circle (2pt); \fill[red] (n51) circle (2pt); \fill[black] (n57) circle (2pt); \fill[black] (n56) circle (2pt); \fill[red] (n50) circle (2pt); \fill[black] (n55) circle (2pt); \fill[black] (n54) circle (2pt); \fill[red] (n49) circle (2pt); \fill[black] (n53) circle (2pt); \fill[black] (n52) circle (2pt); \fill[red] (n5) circle (2pt); \fill[blue] (n28) circle (2pt); \fill[red] (n40) circle (2pt); \fill[black] (n46) circle (2pt); \fill[black] (n45) circle (2pt); \fill[red] (n39) circle (2pt); \fill[black] (n44) circle (2pt); \fill[black] (n43) circle (2pt); \fill[red] (n38) circle (2pt); \fill[black] (n42) circle (2pt); \fill[black] (n41) circle (2pt); \fill[blue] (n27) circle (2pt); \fill[red] (n31) circle (2pt); \fill[black] (n37) circle (2pt); \fill[black] (n36) circle (2pt); \fill[red] (n30) circle (2pt); \fill[black] (n35) circle (2pt); \fill[black] (n34) circle (2pt); \fill[red] (n29) circle (2pt); \fill[black] (n33) circle (2pt); \fill[black] (n32) circle (2pt); \fill[red] (n4) circle (2pt); \fill[blue] (n8) circle (2pt); \fill[red] (n20) circle (2pt); \fill[black] (n26) circle (2pt); \fill[black] (n25) circle (2pt); \fill[red] (n19) circle (2pt); \fill[black] (n24) circle (2pt); \fill[black] (n23) circle (2pt); \fill[red] (n18) circle (2pt); \fill[black] (n22) circle (2pt); \fill[black] (n21) circle (2pt); \fill[blue] (n7) circle (2pt); \fill[red] (n11) circle (2pt); \fill[black] (n17) circle (2pt); \fill[black] (n16) circle (2pt); \fill[red] (n10) circle (2pt); \fill[black] (n15) circle (2pt); \fill[black] (n14) circle (2pt); \fill[red] (n9) circle (2pt); \fill[black] (n13) circle (2pt); \fill[black] (n12) circle (2pt); \draw[dashed] (n12) -- (n129); \node (sup) [right=0.125 of n12] {$s^\up$}; \node (sdown) [right=0.125 of n0] {$s_\down$}; \node (r) [right=0.125 of n1, yshift=-2] {$r$}; \end{tikzpicture} \caption{\label{fig:biregular_tree}The wired $(2,3)$-bi-regular tree $\wiredT[5]_1$ of height $5$ and root of type $1$.} \end{figure} %=============================================================================== \subsection{Rotor-Router Walks}\label{subsec:rr_walks} On a locally finite and connected graph $\G$, a \emph{rotor-router walk} is defined as below. For each vertex $x\in\G$ fix a cyclic ordering $c(x)$ of its neighbours: $c(x)=\big(x^{(0)},x^{(1)},\ldots,x^{(d_x-1)}\big)$, where $x\sim_{\G} x^{(i)}$ for all $i=0,1,\ldots ,d_x-1$ and $d_x$ is the degree of $x$. The ordering $c(x)$ is called the \emph{rotor sequence} of $x$. A \emph{rotor configuration} is a function $\rho: \G\to \G$, with $\rho(x) \sim_{\G} x$, for all $x\in \G$. Hence $\rho$ assigns to every vertex one of its neighbours. By abuse of notation, we write $\rho(x)=i$ if the rotor at $x$ points to the neighbour $x^{(i)}$, with $i\in\{0,1,\ldots,d_x-1\}$. A rotor-router walk is defined by the following rule. Let $x$ be the current position of the particle, and $\rho(x) = i$ the state of the rotor at $x$. In one step of the walk two things happen. First the position of the rotor at $x$ is incremented to point to the next neighbour $x^{(i+1)}$ in the ordering $c(x)$, that is, $\rho(x)$ is set to $i+1$ (with addition performed modulo $d_x$). Then the particle moves to position $x^{(i+1)}$. The rotor-router walk is obtained by repeatedly applying this rule. Suppose now that $\G$ is a finite graph with $m$ vertices and fix a vertex $s$ in $\G$, which will represent the sink. \paragraph*{Rotor-Router Group. } Given a rotor configuration $\rho$ on $\G$, write $e_x(\rho)$ for the rotor configuration resulting from starting a particle at $x$ and letting it perform a rotor-router walk until it reaches the sink $s$. If a particle visits a vertex infinitely often, it also visits all of its neighbours infinitely often; since $\G$ is connected and finite, the particle eventually reaches the sink. The set of edges $\big\{\big(x,\rho(x)\big):x\in \G\setminus\{s\}\big\}$ in a rotor configuration forms a spanning subgraph of $\G$ in which every vertex except the sink $s$ has out-degree one. If this subgraph contains no cycles, we call it an {\em oriented spanning tree} of $\G$. Write $\rec(\G)$ for the set of oriented spanning trees of $\G$, which is also called the set of recurrent configurations. It is easy to see that if $\rho \in\rec(\G)$, then also $e_x(\rho)\in\rec(\G)$. For a proof, see {\sc Landau and Levine} \cite[Lemma 2.1]{landau_levine_2009}. Another interesting property of the rotor configurations is that if $\rho_1,\rho_2\in\rec(\G)$ and $e_x(\rho_1)=e_x(\rho_2)$, then $\rho_1=\rho_2$; see once again \cite{landau_levine_2009} for a proof. This means that the operation $e_x$ of adding a particle at $x$ and routing it to the sink acts invertibly on the set of recurrent rotor configurations. The {\em rotor-router group $\rr(\G)$} of $\G$ is defined as the subgroup of the permutation group of $\rec(\G)$ generated by $\big\{e_x:\: x\in \G\setminus\{s\}\big\}$. For any two vertices $x$ and $y$, the operators $e_x$ and $e_y$ commute. This is the so-called {\em abelian property} of rotor-router walks. Hence the group $\rr(\G)$ is {\em abelian}. Furthermore, $\rr(\G)$ acts transitively on $\rec(\G)$. More details can be found in \cite{landau_levine_2009}. \paragraph*{Sandpile Group.} A {\em chip configuration} $\sigma$ on $\G$, also called a {\em sandpile} on $\G$, is a vector in $\Z^{m-1}$ of non-negative integers indexed by the non-sink vertices of $\G$, where $\sigma(x)$ represents the number of chips at the vertex $x$. A chip configuration $\sigma$ is called {\em stable} if $\sigma(x) 1$ then the limit $\varUpsilon_i=\lim_{h\to\infty}\gamma_i^h$ is positive. \end{lem} Recall that the \emph{spectral radius} $\r(A)$ of a square matrix $A$ is the maximal absolute value of all the eigenvalues of $A$. To prove Lemma \ref{lem:gamma_i} we will need two additional results. \begin{prop} \label{prop:spectral_radius} Let $A\in \R^{m\times m}$ be a non-negative matrix and let $\boldsymbol{v}\in\R^m$ be a positive vector. If there is a number $b\geq 0$ such that $A\boldsymbol{v} \leq b\boldsymbol{v}$, then $\r(A) \leq b$. \end{prop} For the proof see \textsc{Ding and Zhou} \cite[Proposition 2.2]{ding2009nonnegative}. The next result is a simple application of Tarski's Fixed point Theorem for increasing functions on lattices, see \textsc{Kennan} \cite[Theorem 3.3]{kennan_2001}. \begin{thm} \label{thm:concave_fixed_point} Suppose $f$ is an increasing and strictly concave function from $\R^m$ to $\R^m$ such that $f(\boldsymbol{0})\geq \boldsymbol{0}$, $f(\boldsymbol{a})>\boldsymbol{a}$ for some positive vector $\boldsymbol{a}$, and $f(\boldsymbol{b})<\boldsymbol{b}$ for some vector $\boldsymbol{b}>\boldsymbol{a}$. Then $f$ has a unique positive fixed point. \end{thm} \begin{proof}[Proof of Lemma \ref{lem:gamma_i}] Let us fix $i\in\G$ for the rest of the proof. The initial value is $\gamma^1_i=d_i$. Substituting in the definition of $\gamma_i^h$ the recurrence relations \eqref{eq:span_forests} for $F^h_{i,\up}$ and $F^h_{i,\down}$, we get \begin{equation} \label{eq:def_gamma} \gamma_i^h=\sum_{j\in\G} \dfrac{d_{ij}F_{j,\up}^{h-1}}{F_{j,\down}^{h-1}+F_{j,\up}^{h-1}} =\sum_{j\in\G} d_{ij} \dfrac{\gamma_j^{h-1}}{1+\gamma_j^{h-1}}, \text{ for } h\in \N. \end{equation} In order to prove that $\gamma_i^{h}$ is convergent in $h$, we show that $\gamma^h_i$ is monotone and bounded. We first show by induction on $h$ that $\gamma_i^h$ is strictly decreasing. We know that $\gamma^1_i=d_i$, and the induction basis $\gamma^2_i<\gamma^1_i$ follows from \begin{equation*} \gamma^2_i=\sum_{j\in\G} d_{ij} \dfrac{\gamma_j^{1}}{1+\gamma_j^{1}}<\sum_{j\in\G} d_{ij}=d_i=\gamma^1_i. \end{equation*} For the inductive step, we assume that $\gamma^h_i<\gamma^{h-1}_i$, and we prove that $\gamma^{h+1}_i<\gamma^h_i$. This follows from \begin{equation*} \gamma_i^{h+1}=\sum_{j\in\G} d_{ij}\frac{\gamma_j^{h}}{1+\gamma_j^{h}}< \sum_{j\in\G}d_{ij}\frac{\gamma_j^{h-1}}{1+\gamma_j^{h-1}}=\gamma_i^h. \end{equation*} The sequence $\gamma^h_i$ is also bounded, i.e., $0\leq \gamma_i^h 1$ and assume that for all positive vectors $\boldsymbol{a} = (a_1,\ldots,a_m)$ we have $f(\boldsymbol{a}) \leq \boldsymbol{a}$, which can be written as \begin{equation} \label{eq:Da_leq_a} D\begin{pmatrix} \frac{a_1}{1+a_1} \\ \vdots \\ \frac{a_m}{1+a_m} \end{pmatrix} \leq \boldsymbol{a}. \end{equation} Let $a^\star = \max \{a_i: i=1,\ldots,m\}$, then \eqref{eq:Da_leq_a} implies $\frac{1}{1+a^\star} D \boldsymbol{a} \leq \boldsymbol{a}$, hence $D \boldsymbol{a} \leq (1+a^\star)\boldsymbol{a}$, and from Proposition \ref{prop:spectral_radius} it follows that $\r(D) \leq 1 + a^\star$. Since $\boldsymbol{a}$ was arbitrary, $a^\star$ can be made arbitrary small, thus $\r(D) \leq 1$ which is a contradiction to our assumption. Therefore there exists a positive vector $\boldsymbol{a}=(a_1,\ldots,a_m)$ such that $f(\boldsymbol{a}) > \boldsymbol{a}$. Theorem \ref{thm:concave_fixed_point} now ensures the existence of a unique positive fixed point of $f$, hence the equation \eqref{eq:gamma_fixed_point} has a unique positive solution in addition to the trivial solution. It remains to show that the limit vector cannot be zero. Let $\bar{\gamma}^h_i$ be the sequence defined as $\gamma^h_i$ in \eqref{eq:def_gamma} with initial values $\bar{\gamma}^1_i = a_i$. The vector $\boldsymbol{a}$ is such that $f(\boldsymbol{a}) > \boldsymbol{a}$. It is easy to see that the sequence $\bar{\gamma}^h_i$ is increasing and $\gamma_i^{1} - \bar{\gamma}_i^{1}\geq 0$. By induction on $h$, supposing $\gamma_i^{h} - \bar{\gamma}_i^{h}\geq 0$, we get \begin{equation*} \gamma_i^{h+1} - \bar{\gamma}_i^{h+1} = \sum_{j\in\G} d_{ij}\left(\frac{\gamma_j^h}{1+\gamma_j^h} - \frac{\bar{\gamma}_j^h}{1+\bar{\gamma}_j^h}\right) = \sum_{j\in\G} d_{ij} \frac{\gamma_j^h - \bar{\gamma}_j^h}{(1+\gamma_j^h)(1+\bar{\gamma}_j^h)} \geq 0, \end{equation*} therefore $\gamma_i^{h} - \bar{\gamma}_i^{h}$ is non-negative. Hence $\gamma_i^h$ is bounded from below by $\bar{\gamma}_i^h$, and the limit $\varUpsilon_i$ is positive. \end{proof} \begin{thm} \label{thm:asymptotics_rrorder} Let $\G$ be a finite, directed and strongly connected graph with vertex set $\{1,2,\ldots,m\}$ and adjacency matrix $D$. Let $\T_i$ be the directed cover of $\G$ with root $r$ of type $i$ and $\wiredT_i$ be the wired tree defined as above. If $\r(D)>1$, then the order of the rotor-router group $\rr(\wiredT_i)$ grows doubly exponential: \begin{equation} \log \big|\rr(\wiredT_i)\big|\asymp \r(D)^h,\quad \text{ for all } i\in\G, \end{equation} where $\r(D)$ is the spectral radius (Perron-Frobenius eigenvalue) of $D$. \end{thm} \begin{proof} Recall first that $ \big|\rr(\wiredT_i)\big|=F^h_{i,\down}+F^h_{i,\up}$. In order to simplify the system of equations \eqref{eq:span_forests} let us make the following substitution: for $i\in\G$ denote by $x_i^h=\log F^h_{i,\down}$ and $y_i^h=\log F^h_{i,\up}$ and apply the logarithm function to \eqref{eq:span_forests}. We get \begin{equation}\label{eq:log_spanning_forests} \begin{eqsystem} x_i^h & = \sum_{j\in\G} d_{ij}x_j^{h-1}+\sum_{j\in\G} d_{ij}\log\big(1+\gamma_j^{h-1}\big) \\ y_i^h & = x_i^h+\log\big(\gamma_i^h\big). \end{eqsystem} \end{equation} Consider now the following vectors in $\R^m$: \begin{equation*} \boldsymbol{x}^h= \begin{pmatrix} x_1^h \\ \vdots \\x_m^h \end{pmatrix}, \quad \quad \boldsymbol{y}^h=\begin{pmatrix} y_1^h \\ \vdots \\y_m^h \end{pmatrix}, \quad \quad \boldsymbol{\gamma}^h=\begin{pmatrix} \gamma_1^h \\ \vdots \\ \gamma_m^h \end{pmatrix}. \end{equation*} Then \eqref{eq:log_spanning_forests} can be written in matrix form as \begin{equation}\label{eq:vector_spanning_forests} \begin{eqsystem} \boldsymbol{x}^h &= D\Big(\boldsymbol{x}^{h-1}+\log\big(1+\boldsymbol\gamma^{h-1}\big)\Big)\\ \boldsymbol{y}^h &= \boldsymbol{x}^h+\log\big(\boldsymbol{\gamma}^h\big), \end{eqsystem} \end{equation} where the function $\log$ in \eqref{eq:vector_spanning_forests} is applied componentwise to the entries of the vectors $\boldsymbol\gamma^h$ and $(1+\boldsymbol\gamma^h)$ respectively. The initial values are $\boldsymbol{x}^1=(0,\ldots,0)^T$, $\boldsymbol{y}^1=(\log d_1, \ldots, \log d_m)^T$, and $\boldsymbol\gamma^1=(d_1,\ldots, d_m)^T$. Then the solution of \eqref{eq:vector_spanning_forests} is given by \begin{equation} \boldsymbol{x}^h=\sum_{k=1}^{h-1}D^k\log (1+\boldsymbol\gamma^{h-k}). \end{equation} From Lemma \ref{lem:gamma_i} the entries of the vector $\log\big(1+\boldsymbol\gamma^{h-k}\big)$ are bounded: for all $i\in\{1,2,\ldots,m\}$ and $k=1,\ldots,h$ \begin{equation*} 0<\log(1+\varUpsilon_i)\leq\log (1+\gamma_i^{h-k})\leq\log(1+\gamma_i^1)=\log(1+d_i). \end{equation*} All $\varUpsilon_i$ and $d_i$ are positive. Write $c_i=\log(1+\varUpsilon_i)$ and $C_i=\log(1+d_i)$. Then \begin{equation}\label{eq:Xh} \left(\sum_{k=1}^{h-1}D^k\right)\boldsymbol{c} \leq \boldsymbol{x}^h \leq \left(\sum_{k=1}^{h-1}D^k\right)\boldsymbol{C}, \end{equation} where $\boldsymbol{c}=(c_1,\ldots,c_m)^T$ and $\boldsymbol{C}=(C_1,\ldots,C_m)^T$. The sum $\left(\sum_{k=1}^{h-1}D^k\right)$ behaves like $D^h$ for big values of $h$, and the exponential growth rate of the matrix power $D^h$ as $h\to\infty$ is controlled by the eigenvalue of $D$ with the largest absolute value. Since $D$ is a non-negative and irreducible matrix, according to Perron-Frobenius theorem for irreducible matrices, there exists a positive real number $\r(D)$ (the spectral radius of $D$), called the {\em Perron-Frobenius eigenvalue} which is the eigenvalue of $D$ with the largest absolute value. %The eigenvalue %$\lambda$ is also simple, and it satisfies %\begin{equation*} %\min_i d_i\leq \lambda \leq \max_i d_i, %\end{equation*} %where $d_i=\sum_{j\in\G}d_{ij}$. Because of the irreducibility, $\min_i d_i\geq 1$, therefore %the Perron-Frobenius eigenvalue of $D$ is greater that $1$. By \eqref{eq:Xh}, we can conclude that the behaviour of $\boldsymbol{x}^h$, for $h\to\infty$ is given by the greatest eigenvalue $\r(D)>1$ of $D$, i.e., for all $i$ \begin{equation*} x_i^h\asymp \r(D)^h. \end{equation*} Since $\boldsymbol{y}^h$ differs from $\boldsymbol{x}^h$ only by a bounded and decreasing quantity, see \eqref{eq:vector_spanning_forests}, it holds $y_i^h\asymp \r(D)^h$. Using \begin{align*} \log \big|\rr(\wiredT_i)\big| & = \log\left(F_{i,\down}^h+F_{i,\up}^h\right)=\log\left(F_{i,\down}^h\big(1+\gamma_i^h\big)\right)\\ & =x_i^h+ \log \big(1+\gamma_i^h\big). \end{align*} and Lemma \ref{lem:gamma_i}, we get the desired. \end{proof} \begin{exam}[The Fibonacci tree] For the Fibonacci tree, the system of equations \eqref{eq:span_forests} can be written as \begin{equation*} \begin{eqsystem} F^h_{1,\down} &= F^{h-1}_{2,\down}+F^{h-1}_{2,\up}\\ F^h_{1,\up} &= F^{h-1}_{2,\up}\\ \end{eqsystem} \quad \quad \begin{eqsystem} F^h_{2,\down} &= \big(F^{h-1}_{1,\down}+F^{h-1}_{1,\up}\big)\big(F^{h-1}_{2,\down}+F^{h-1}_{2,\up}\big)\\ F^h_{2,\up} &= F^{h-1}_{1,\up}\big(F^{h-1}_{2,\down}+F^{h-1}_{2,\up}\big)+F^{h-1}_{2,\down}\big(F^{h-1}_{1,\down}+F^{h-1}_{1,\up}\big)\\ \end{eqsystem} \end{equation*} The two sequences $\gamma^h_1$ and $\gamma^h_2$ are given recursively by \begin{equation*} \gamma^h_1=\dfrac{\gamma_2^{h-1}}{1+\gamma_2^{h-1}} \quad \text{ and } \quad \gamma_2^h= \dfrac{\gamma_1^{h-1}}{1+\gamma_1^{h-1}} +\dfrac{\gamma_2^{h-1}}{1+\gamma_2^{h-1}}. \end{equation*} The initial values are $\gamma^1_1=1$, $\gamma^1_2=2$ and the limit values are \begin{equation*} \varUpsilon_1=\lim_{h\to\infty}\gamma^h_1=\sqrt{2}-1 \quad \text{ and } \quad \varUpsilon_2=\lim_{h\to\infty}\gamma^h_2=\frac{\sqrt{2}}{2}. \end{equation*} The Perron-Frobenius eigenvalue of $D$ is $\frac{1+\sqrt{5}}{2}$, which is also related with the Fibonacci numbers $\mathsf{F}_n$ by $\lim_{n\to\infty}\frac{\mathsf{F}_{n+1}}{\mathsf{F}_n}=\frac{1+\sqrt{5}}{2}$. Finally, regarding the order of the rotor-router group $\rr(\wiredT_i)$ we have \begin{equation*} \log\big|\rr(\wiredT_i)\big|\asymp \Bigg(\frac{1+\sqrt{5}}{2}\Bigg)^h. \end{equation*} \end{exam} \subsection{Order of the Root Element in the Rotor-Router Group} \textsc{Levine} \cite{levine_sandpile_tree} computed the order of the root element in the rotor-router group on homogeneous trees. His approach holds only for homogeneous trees, and it fails in our case. We describe here the order of the root element in terms of the respective orders on the principal subbranches. Our method is yet another useful application of the {\em explosion formula} introduced in \cite[Theorem 11]{angel_holroyd_2011}. Like before, $\T_i$ is the directed cover of $\G$ with root $r$ of type $\tau(r)=i$. The {\em principal branches} of $\T_i$ are the subtrees $\T_{\chi_i(k)}$ rooted at the children $r^{(k)}$ of the root $r$ with type $\chi_i(k)=\tau(r^{(k)})$ and $k=1,2,\ldots, d_i$. Hence $\T_i$ has as principal branches $d_i=\sum_{j\in\G} d_{ij}$ subtrees. Recall the definition of the truncated wired tree $\wiredT_i$, with the same root $r$ and sink $S=s_{\down}\cup s^{\up}$. Suppose now that we have one particle at the root $r$ of $\wiredT_i$, and we let it perform a rotor-router walk until it hits the sink $S$, where it stops. Denote by $\hat{r}_h$ the element of the rotor-router group $\rr(\wiredT_i)$ corresponding to this process. Similarly, for all $k=1,\ldots,d_i$, denote by $\hat{r}^{(k)}_{h-1}$ the element of the rotor-router group $\rr\big(\widetilde{\mathcal{T}}^{h-1}_{\chi_i(k)}\big)$ corresponding to one particle performing rotor-router walk on the principal subbranch $\widetilde{\mathcal{T}}^{h-1}_{\chi_i(k)}$ starting at $r^{(k)}$. Write $\langle\hat{r}_h \rangle$ for the cyclic subgroup of $\rr(\wiredT_i)$ generated by $\hat{r}_h$, and $\big\langle \big(\hat{r}^{(1)}_{h-1} ,\ldots ,\hat{r}^{(d_i)}_{h-1}\big) \big\rangle$ for the cyclic subgroup of $\bigoplus_{k=1}^{d_i}\rr\big(\widetilde{\mathcal{T}}^{h-1}_{\chi_i(k)}\big)$ generated by the element $\big(\hat{r}^{(1)}_{h-1} ,\ldots ,\hat{r}^{(d_i)}_{h-1}\big)$. By \cite[Theorem 3.3]{levine_sandpile_tree} and from the isomorphism between the sandpile and the rotor-router group of a tree, we have \begin{equation} \rr(\wiredT_i)/\langle\hat{r}_h \rangle \simeq \bigoplus_{k=1}^{d_i} \widetilde{\mathcal{T}}^{h-1}_{\chi_i(k)}\Big/ \big\langle \big(\hat{r}^{(1)}_{h-1} ,\ldots ,\hat{r}^{(d_i)}_{h-1}\big) \big\rangle \end{equation} For simplicity of notation, we denote by $R^h_i$ the {\em order of the element $\hat{r}_h$} in the rotor-router group $\rr(\wiredT_i)$, that is, the cardinality of the cyclic group $\langle\hat{r}_h \rangle$, i.e. $ R_i^h=|\langle\hat{r}_h \rangle|$. Recall the definition of the down and up sinks $s_{\down}$ and $s^{\up}$ respectively and let \begin{center} $S^h_{i,\down} =$ \begin{minipage}[t]{0.6\linewidth} the number of particles stopped in $s_{\down}$ after $R_i^h$ particles have been routed from $r$, \end{minipage} $S^h_{i,\up} =$ \begin{minipage}[t]{0.6\linewidth} the number of particles stopped in $s^{\up}$ after $R_i^h$ particles have been routed from $r$, \end{minipage} \end{center} for $i\in\G$. Then \begin{equation}\label{eq:sum_root_order} R_i^h=S^h_{i,\down}+S^h_{i,\up}. \end{equation} Write $R^{h-1}_{\chi_i(k)}$ for the number of particles started at the origin $r^{(k)}$ of the branch $\T^{h-1}_{\chi_i(k)}$. \begin{thm}\label{thm:root_element_order} The order $ R_i^h$ of the root element in the rotor-router group is given by $R_i^h=S^h_{i,\down}+S^h_{i,\up}$ and $S^h_{i,\down},S^h_{i,\up}$ can be computed recursively as follows: \begin{equation}\label{eq:root_order_simplified} \begin{eqsystem} S^h_{i,\down} &= \lcm\Big(\Big\{R^{h-1}_{\chi_i(k)}: \text{ for }k=1,\ldots,d_i\Big\}\Big) \\ S^h_{i,\up} &= S^h_{i,\down} \sum_{j\in\G}d_{ij}\dfrac{S^{h-1}_{j,\up}}{R^{h-1}_{j}}, \end{eqsystem} \end{equation} for all $i\in\G$. Here $\lcm$ represents the least common multiple. The starting values are given by $S^1_{i,\down} = 1$ and $S^1_{i,\up}=d_i$, for all $i\in\G$. \end{thm} The proof of this result uses the \emph{explosion formula} introduced in \cite[Theorem 11]{angel_holroyd_2011}. Since we will need this formula in the proof, we first adapt it here to our case. \subsubsection{Explosion Formula} The explosion formula, introduced in \cite[Theorem 11]{angel_holroyd_2011}, gives a recursive formula for computing the number $E_n(\T_i,\rho)$ of particles which escape to infinity when we start $n$ rotor-router walks at the root $r$ of a tree $\T_i$. The initial configuration of rotors on $\T_i$ is $\rho$. For the tree $\T_i$ and principal branches $\T_{\chi_i(k)}$, rooted at the children $r^{(k)}$ of $r$, write $\rho_{\chi_i(k)}$ for the restriction of the rotor configuration $\rho$ on $\T_{\chi_i(k)}$, with $k=1,\ldots,d_i$. Let us first introduce some notations, following mainly the notations from \cite[Theorem 11]{angel_holroyd_2011}. Let $e_n=e_n(\T_i,\rho)=\indicator{[\text{particle } n \text{ escapes to infinity}]}$, where $\indicator{}$ represents the indicator function, so that $E_n=\sum_{k=1}^ne_k$. Moreover, let $e(\T_i,\rho)$ be the {\em escape sequence} $(e_1,e_2,\ldots)$. Let $\N_+=\{1,2,\ldots\}$ and for sequences in $\N^{\N_+}$ we denote addition by $(a_1,a_2,\ldots)+(b_1,b_2,\ldots):=(a_1+b_1,a_2+b_2,\ldots)$. Define the {\em shift operator } $\theta$ by \begin{equation*} \theta(a_1,a_2,\ldots):=(0,a_1,a_2,\ldots) \end{equation*} and the {\em explosion operator} $\mathfrak{X}$ by \begin{equation*} \mathfrak{X}(a_1,a_2,\ldots):=(1^{a_1},0,1^{a_2},0,\ldots) \end{equation*} where $1^k$ denotes a string of $k$ $1$s, or the empty string if $k=0$. We define a {\em majorization} order $\preceq$ on sequences $(a_1,a_2,\ldots)\preceq(b_1,b_2,\ldots)$ if and only $\sum_1^n a_j\leq \sum_1^n b_j$ for all $n$. For $\mathbf{a}=(a_1,a_2,\ldots)$ denote by $\mathbf{a}_k = a_k$ its $k$-th element. For a finite sequence $\mathbf{a}$ the length is denoted by $\abs{\mathbf{a}}$ and $\mathbf{a}^n$ is its $n$ times repetition. We now adapt \cite[Theorem 11]{angel_holroyd_2011} for directed covers of finite graphs. \begin{thm}[Explosion formula] Let $\G$ be a finite graph with $m$ vertices and $\T_i$ its directed cover with root $r$ of type $i$. Fix a rotor configuration $\rho$ on $\T_i$. Then \begin{equation*} e(\T_i,\rho)=\mathfrak{X}\Bigg(\sum_{k=1}^{\rho(r)}\theta e\big(\T_{\chi_i(k)},\rho_{\chi_i(k)}\big)+ \sum_{k=\rho(r)+1}^{d_i}e\big(\T_{\chi_i(k)},\rho_{\chi_i(k)}\big)\Bigg). \end{equation*} \end{thm} \begin{rem} In case of a finite tree $\T^h_i$, we define the escape sequence $e$ such that $e_n(\T^h_i,\rho)=1$ if the $n$-th particle reaches the upper sink $s^\up$ before reaching $s_\down$, and $0$ otherwise. Then the explosion formula can be also written in the form \begin{equation*} e(\T^h_i,\rho)=\mathfrak{X}\Bigg(\sum_{k=1}^{\rho(r)}\theta e\big(\T^{h-1}_{\chi_i(k)},\rho_{\chi_i(k)}\big)+ \sum_{k=\rho(r)+1}^{d_i}e\big(\T^{h-1}_{\chi_i(k)},\rho_{\chi_i(k)}\big)\Bigg), \end{equation*} with initial values $e(\T^0_i,\rho) = (1,1,\ldots)$ for all $i\in\G$. \end{rem} \begin{proof}[Proof of Theorem \ref{thm:root_element_order}] Fix an $i\in\G$. As in the proof of Theorem \ref{thm:recurent_rotor_group} let $\T^h_i$ be a tree with root $r$ of type $i\in\G$, and of height $h$. For $k = 1,\ldots,d_i$, we denote by $\T^{h-1}_{\chi_i(k)}$ the cone of the $k$-th child $r^{(k)}$ of the root $r$ in $\T^h_i$. By the construction of the directed cover, the root $r^{(k)}$ of $\T^{h-1}_{\chi_i(k)}$ is of type $\chi_i(k)$. % We first prove that % \begin{equation}\label{eq:root_order} % \begin{eqsystem} % S^h_{i,\down} &= \lcm(R^{h-1}_{1},\ldots,R^{h-1}_{d_i}) \\ % S^h_{i,\up} &= S^h_{i,\down} \sum_{k=1}^{d_i}\dfrac{S^{h-1}_{k,\up}}{R^{h-1}_{k}}, % \end{eqsystem} % \end{equation} % and then we show that this is equivalent with \eqref{eq:root_order_simplified}. It is enough to consider only the zero rotor configuration $\underline{0}$, that is, at all vertices the rotors point to the ancestors. Recall that $R^h_i$ is the order of the root element in the rotor-router group of $\T^h_i$. Hence, after $R^h_i$ particles have performed a rotor-router walk (stopped at the sink $S$) we are back to the configuration $\underline{0}$. In other words, the escape sequence $e(\T^h_i, \underline{0})$ is periodic with period $R^h_i$. Write $\mathbf{e}(\T^h_i)$ for the finite sequence consisting of the first full period of $e(\T^h_i, \underline{0})$. Using the explosion formula we can write $\mathbf{e}(\T^h_i)$ in terms of the escape sequences of the principal subtrees $\T^{h-1}_{\chi_i(k)}$, with $i=1,\ldots,d_i$. In order to adapt the explosion formula to the finite sequence $\mathbf{e}(\T^h_i)$, all the escape sequences involved need to be extended such that they have the same length, the common length being the least common multiple $\lcm\left(R^{h-1}_{\chi_i(1)},\ldots,R^{h-1}_{\chi_i(d_i)}\right)$ of orders of the root elements of the principal branches. Let now \begin{equation*} f^{h-1}_i(k) := \frac{\lcm\left(R^{h-1}_{\chi_i(1)},\ldots,R^{h-1}_{\chi_i(d_i)}\right)}{R^{h-1}_{\chi_i(k)}} . %= \frac{S^h_{i,\down}}{R^h_{\chi_i(k)}}, \end{equation*} be the number of repetitions needed for the escape sequence $\mathbf{e}\big(\T^{h-1}_{\chi_i(k)}\big)$. We can then write the explosion formula for the first $R^h_i$ particles as \begin{equation} \label{eq:explosion_finite_sequence} \mathbf{e}(\T^h_i) = \mathfrak{X}\left(\mathbf{v}^{h-1}_i\right) \quad \text{ with } \quad \mathbf{v}^{h-1}_i = \sum_{k=1}^{d_i}\mathbf{e}\big(\T^{h-1}_{\chi_i(k)}\big)^{f^{h-1}_i(k)}. %\mathfrak{X}\left(\sum_{k=1}^{d_i}\mathbf{e}\big(\T^{h-1}_{\chi_i(k)}\big)^{f^{h-1}_i(k)}\right) \end{equation} Hence $\mathbf{e}(\T^h_i)$ is a sequence of length $R^h_i = S^h_{i,\down} + S^h_{i,\up}$ consisting of ''zeros`` and ''ones``, with $S^h_{i,\down}$ being the number of $0$'s and $S^h_{i,\up}$ being the number of $1$'s. Since the number of $0$'s in a string $\mathfrak{X}(\mathbf{a})$ is equal to $\abs{\mathbf{a}}$, we get \begin{equation*} S^h_{i,\down} = \abs{\mathbf{v}^{h-1}_i} = \lcm\left(R^{h-1}_{\chi_i(1)},\ldots,R^{h-1}_{\chi_i(d_i)}\right). \end{equation*} On the other hand, because $S^h_{i,\up}$ equals the number of $1$'s in the escape sequence $\mathbf{e}(\T^h_i)$, the explosion formula \eqref{eq:explosion_finite_sequence} gives \begin{equation}\label{eq:Shi_expansion} S^h_{i,\up} = \sum_{\ell=1}^{R^h_i} \mathbf{e}(\T^h_i)_{\ell} = \sum_{\ell=1}^{R^h_i} \mathfrak{X}\left(\mathbf{v}^{h-1}_i\right)_\ell = \sum_{\ell=1}^{S^h_{i,\down}} \left(\sum_{k=1}^{d_i}\mathbf{e}\big(\T^{h-1}_{\chi_i(k)}\big)^{f^{h-1}_i(k)}\right)_\ell. \end{equation} In the last equality we used the fact that for any finite sequence $\mathbf{a}$, $\sum_{\ell=1}^{\abs{\mathbf{a}}} \mathbf{a}_\ell = \sum_{\ell=1}^{\abs{\mathfrak{X}(\mathbf{a})}} \mathfrak{X}(\mathbf{a})_\ell$ holds. By exchanging the order of summation in \eqref{eq:Shi_expansion}, we obtain \begin{align*} S^h_{i,\up} &= \sum_{k=1}^{d_i} \sum_{\ell=1}^{S^h_{i,\down}} \left(\mathbf{e}\big(\T^{h-1}_{\chi_i(k)}\big)^{f^{h-1}_i(k)}\right)_\ell = \sum_{k=1}^{d_i} f^{h-1}_i(k) \sum_{\ell=1}^{R^{h-1}_{\chi_i(k)}} \mathbf{e}\Big(\T^{h-1}_{\chi_i(k)}\Big)_\ell \\ &= \sum_{k=1}^{d_i} f^{h-1}_i(k) S^{h-1}_{\chi_i(k),\up} = S^h_{i,\down}\sum_{k=1}^{d_i} \frac{S^{h-1}_{\chi_i(k),\up}}{R^{h-1}_{\chi_i(k)}} = S^h_{i,\down}\sum_{j\in\G} d_{ij} \frac{S^{h-1}_{j,\up}}{R^{h-1}_j}, \end{align*} which proves the theorem. \end{proof} We give now an alternative way of writing the system \eqref{eq:root_order_simplified}. Using \eqref{eq:sum_root_order}, let us add the two equations in \eqref{eq:root_order_simplified}, and then divide the result through $R^h_i$. We get \begin{equation}\label{eq:alternative_root_order} \begin{eqsystem} S^h_{i,\down} &= \lcm\Big(\Big\{R^{h-1}_{\chi_i(k)}: \text{ for }k=1,\ldots,d_i\Big\}\Big) \\ 1 &= \dfrac{S^h_{i,\down}}{R^h_i}\Bigg(d_i+1-\sum_{j\in\G}d_{ij}\dfrac{S^{h-1}_{j,\down}}{R^{h-1}_{j}}\Bigg) \end{eqsystem} \end{equation} Because of the $\lcm$ involved in \eqref{eq:root_order_simplified}, it is hard to derive asymptotics for $R_i^h$. \paragraph*{Connection with the Random Walk.} Let $(X_t)$ be a simple random walk on $\T_i$ which starts at the root $r$ of $\T_i$ and define the {\em stopping times} $\sigma_i$ (which depend on the root $r$ with type $\tau(r)=i$) as \begin{equation*} \sigma_i=\inf\{t\geq 0: X_t\in s_{\down}\cup s^{\up}\} \end{equation*} and {\em hitting probabilities} $H_{i,\down}$ and $H_{i,\up}$ as \begin{equation}\label{eq:hit_times} H_{i,\down}=\P_{r}[X_{\sigma_i}=s_{\down}] \quad \text{ and } \quad H_{i,\up}=\P_{r}[X_{\sigma_i}\in s^{\up}] \end{equation} Write $H^h_{i,\down}$ and $H^h_{i,\up}$ for the corresponding probabilities on the truncated tree $\T^h_i$. It is easy to see that $H_{i,\down}$ (or $H_{i,\up}$) can be expressed as the quotient between the number of particles $S^h_{i,\down}$ (or $S^h_{i,\up}$) that are routed in the sink $s_{\down}$ (or $s^{\up}$) and the total number of particles $R_i^h$ started at the root, that is \begin{equation*} H_{i,\down}=\dfrac{S^h_{i,\down}}{R^h_i} \quad \text{ and } \quad H_{i,\up}=\dfrac{S^h_{i,\up}}{R^h_i}. \end{equation*} One can also obtain that $H_i$ is the solution of the same equation \eqref{eq:alternative_root_order}, by factorizing the random walk $(X_t)$ with respect to the first step \begin{equation}\label{eq:hit_prob} 1=H^h_{i,\down}\Big(d_i+1-\sum_{k=1}^{d_{i}}H^{h-1}_{\chi_i(k),\down}\Big)=H^h_{i,\down}\Big(d_i+1-\sum_{j=1}^{m}d_{ij}H^{h-1}_{j,\down}\Big), \end{equation} with the initial value $H^1_{i,\down}=1/(d_i+1)$. \begin{exam}[Fibonacci Tree] Consider the order of the root element in the rotor-router group $\rr(\wiredT_i)$ of the wired Fibonacci tree $\wiredT_i$. In this case the equation \eqref{eq:alternative_root_order} is given as: \begin{equation*} \begin{eqsystem} S^h_{1,\down} & =R^{h-1}_2\\ R^h_1 & = S^h_{1,\down}\left(2-\dfrac{S^{h-1}_{2,\down}}{R^{h-1}_2}\right) \end{eqsystem} \quad \quad \quad \quad \begin{eqsystem} S^h_{2,\down} & = \lcm \big(R^{h-1}_1,R^{h-1}_2\big)\\ R^h_2 & = S^h_{2,\down}\left(3-\dfrac{S^{h-1}_{1,\down}}{R^{h-1}_1}-\dfrac{S^{h-1}_{2,\down}}{R^{h-1}_2}\right) \end{eqsystem} \end{equation*} Computations suggest that on the Fibonacci tree, the sequences $S^h_{i,\down}$ and $R_i^h$ are relatively prime. \end{exam} \begin{exam}[Bi-regular tree] For the $(\alpha,\beta)$-bi-regular tree the recurrence relation \eqref{eq:alternative_root_order} for the order of the root element reduces to the simple form \begin{align*} R^h_1 & = R^{h-1}_2(\alpha + 1) - \alpha R^{h-2}_1 \\ R^h_2 & = R^{h-1}_1(\beta + 1) - \beta R^{h-2}_2, \end{align*} which has the explicit solution \begin{equation*} R^h_1 = \begin{cases} \dfrac{(\alpha \beta)^k - 1}{\alpha\beta - 1} (\alpha + 1)\beta + 1, & \text{ for } h = 2k \\[1em] \dfrac{(\alpha\beta)^{k+1} - 1}{\alpha\beta - 1}(\alpha + 1), & \text{ for } h = 2k + 1. \end{cases} \end{equation*} For $R^h_2$ the solution is the same, with the roles of $\alpha$ and $\beta$ exchanged. \end{exam} \paragraph*{Acknowledgements.} We are grateful to Elmar Teufl for useful disscusions, and also to the referees whose comments and suggestions improved the paper. %=================================================================================================== \newcommand{\etalchar}[1]{$^{#1}$} \begin{thebibliography}{HLM{\etalchar{+}}08} \bibitem[AH11]{angel_holroyd_2011} O.~Angel and A.~E. Holroyd, \textsl{ Rotor walks on general trees}, \newblock SIAM J. Discrete Math. \textbf{ 25}(1), 423--446 (2011). \bibitem[CDFS06]{cooper_doerr_friedrich_spencer_2006} J.~Cooper, B.~Doerr, T.~Friedrich and J.~Spencer, \textsl{ Deterministic random walks}, \newblock Proceedings of the Workshop on Analytic Algorithmics and Combinatorics , 185--197 (2006). \bibitem[CS06]{cooper_spencer_2006} J.~N. Cooper and J.~Spencer, \textsl{ Simulating a Random Walk with Constant Error}, \newblock Combinatorics, Probability and Computing \textbf{ 15}, 815--822 (2006). \bibitem[DF06]{doerr_friedrich_2007} B.~Doerr and T.~Friedrich, \newblock Deterministic Random Walks on the Two-Dimensional Grid, \newblock in \textsl{ ISAAC}, edited by T.~Asano, volume 4288 of \textsl{ Lecture Notes in Computer Science}, pages 474--483, Springer, 2006. \bibitem[DZ09]{ding2009nonnegative} J.~Ding and A.~Zhou, \newblock \textsl{ Nonnegative matrices, positive operators, and applications}, \newblock World Scientific, 2009. \bibitem[HLM{\etalchar{+}}08]{chip_rotor_2008} A.~E. Holroyd, L.~Levine, K.~M{\'e}sz{\'a}ros, Y.~Peres, J.~Propp and D.~B. Wilson, \newblock Chip-firing and rotor-routing on directed graphs, \newblock in \textsl{ In and out of equilibrium. 2}, volume~60 of \textsl{ Progr. Probab.}, pages 331--364, Birkh\"auser, Basel, 2008. \bibitem[HP10]{holroyd_propp} A.~E. Holroyd and J.~Propp, \newblock {R}otor {W}alks and {M}arkov {C}hains, \newblock in \textsl{ Algorithmic Probability and Combinatorics}, edited by M.~M. M.~E.~Lladser, Robert S.~Maier and A.~Rechnitzer, volume 520 of \textsl{ Contemporary Mathematics}, pages 105--126, 2010. \bibitem[HS11]{huss_sava_rotor} W.~Huss and E.~Sava, \textsl{ Rotor-Router Aggregation on the Comb}, \newblock Electronic Journal of Combinatorics \textbf{ 18} (2011), \#P224. \bibitem[HS12]{huss_sava_transience_dircovers} W.~Huss and E.~Sava, \newblock Transience and recurrence of rotor-router walks on directed covers of graphs, \newblock preprint, 2012. \bibitem[Ken01]{kennan_2001} J.~Kennan, \textsl{ Uniqueness of Positive Fixed Points for Increasing Concave Functions on $\mathbb{R}^n$: An Elementary Result}, \newblock Review of Economic Dynamics \textbf{ 4}(4), 893 -- 899 (2001). \bibitem[Kle05]{kleber_goldbug} M.~Kleber, \textsl{ Goldbug variations}, \newblock Math. Intelligencer \textbf{ 27}(1), 55--63 (2005). \bibitem[Lev09]{levine_sandpile_tree} L.~Levine, \textsl{ The sandpile group of a tree}, \newblock Eur. J. Comb. \textbf{ 30}(4), 1026--1035 (2009). \bibitem[LL09]{landau_levine_2009} I.~Landau and L.~Levine, \textsl{ The rotor-router model on regular trees}, \newblock J. Combin. Theory Ser. A \textbf{ 116}(2), 421--433 (2009). \bibitem[LP]{LP:book} R.~Lyons with Y.~Peres, \newblock \textsl{ Probabilty on trees and networks}, \newblock preprint. \url{http://mypage.iu.edu/~rdlyons/}. \bibitem[NW02]{woess_nagnibeda} T.~Nagnibeda and W.~Woess, \textsl{ Random walks on trees with finitely many cone types}, \newblock J. Theoret. Probab. \textbf{ 15}(2), 383--422 (2002). \bibitem[PDDK96]{PhysRevLett.77.5079} V.~B. Priezzhev, D.~Dhar, A.~Dhar and S.~Krishnamurthy, \textsl{ Eulerian Walkers as a Model of Self-Organized Criticality}, \newblock Phys. Rev. Lett. \textbf{ 77}(25), 5079--5082 (Dec 1996). \bibitem[Tak97]{Takacs97randomwalk} C.~Takacs, \textsl{ Random Walk on Periodic Trees}, \newblock Electron J. Probab \textbf{ 2} (1997). \end{thebibliography} \end{document}