We prove that on any transitive graph $G$ with infinitely many ends, a self-avoiding walk of length $n$ is ballistic with extremely high probability, in the sense that there exist constants $c,t>0$ such that $\mathbb{P}_n(d_G(w_0,w_n)\geq cn)\geq 1-e^{-tn}$ for every $n\geq 1$. Furthermore, we show that the number of self-avoiding walks of length $n$ grows asymptotically like $\mu_w^n$, in the sense that there exists $C>0$ such that $\mu_w^n\leq c_n\leq C\mu_w^n$ for every $n\geq 1$. Our results extend more generally to quasi-transitive graphs with infinitely many ends, satisfying the additional technical property that there is a quasi-transitive group of automorphisms of $G$ which does not fix an end of $G$.

§ INTRODUCTION

A self-avoiding walk on a graph $G$ is a walk that visits each vertex at most once. This notion was originally introduced in the work of the chemist Flory [12] to model long polymer chains, and it soon attracted the interest of the mathematical community. The primary focus has been on studying the asymptotic behaviour of a self-avoiding of a given length sampled uniformly at random, giving rise to questions that, while simple to pose, frequently prove challenging to resolve.

A significant amount of research on self-avoiding walks has concentrated on answering these questions in the case of lattices in $\mathbb{R}^d$, where the model is now well-understood in dimensions $d\geq 5$ by the seminal work of Hara and Slade [30, 31]. The low-dimensional cases continue to present serious challenges. See [29, 33, 34, 8, 7, 6, 9, 35] and the references therein for some of the most important results. For a comprehensive introduction to the model in this context interested readers can refer to [2, 38].

Over the years, the study of self-avoiding walk beyond lattices has received increasing attention. The systematic study of self-avoiding walk on general transitive graphs was initiated in a series of papers by Grimmett and Li [15, 20, 16, 17, 21, 18, 19, 23], whose work is primarily concerned with properties of the connective constant.
Other works on self-avoiding walk in this context include [39, 40, 22, 14, 3, 37, 41, 4, 13].
See [23] for a survey of these results.

In this paper, we consider the self-avoiding walk on quasi-transitive graphs with more than one end. Such graphs admit a group invariant tree decomposition $\Tcal = (T,\Vcal)$; we refer the reader to Section <ref> for the precise definition, but note that any such tree decomposition gives rise a quasi-transitive action of $\AUT(G)$ on $T$. The concept of tree decomposition was initially introduced by Halin in 1976 [26] and later rediscovered by Robertson and Seymour [42], playing a pivotal role in proving the Graph Minor Theorem. Tree decompositions that are invariant under some group action were perhaps first studied by Dunwoody and Krön [11], drawing inspiration from a method involving edge cuts introduced by Dunwoody in [10]. In our context, it is crucial that these tree decompositions are not only invariant under a quasi-transitive group of automorphisms, but also satisfy some additional properties – see Corollary <ref> for the precise statement.

One of the first instances in the study of self-avoiding walks on graphs with more than one end can be found in the work of Alm and Janson [1], where they specifically study the case of $2$-ended graphs. This particular case turns out to be more tractable due to the fact that the large-scale structure of the graph is similar to that of a line, that is, the tree $T$ of the tree decomposition is isomorphic to $\mathbb Z$. The remaining case of graphs with infinitely many ends proves to be more challenging, with the currently known results limited to either the properties of the SAW-generating functions away from its critical point [36] or to graphs that satisfy additional geometric assumptions [14, 37]. Our main results answer two fundamental questions in the study of self-avoiding walks in the case of transitive graphs with infinitely many ends, and more generally, quasi-transitive graphs $G$ that satisfy the additional technical property that a quasi-transitive group of automorphisms $\Gamma$ of $G$ does not fix an end of the tree $T$; this is in particular true if $\AUT(G)$ does not fix an end of $G$.

Denote by $c_n$ the number of self-avoiding walks of length $n$ on $G$
started from some fixed vertex $o$. A fundamental quantity in the study of self-avoiding walk is the connective constant
$$\mu_w=\lim_{n\to \infty} c_n^{1/n},$$

where the fact that the limit exists and does not depend on the starting point follows from a standard subadditivity argument [28]. The connective constant is not typically known or expected to take an interesting value, with a notable exception being the hexagonal lattice, where Duminil-Copin and Smirnov proved in a celebrated paper [9] that $\mu_w=\sqrt{2+\sqrt{2}}$. For this reason, it is often more interesting to estimate the subexponential correction to $\mu_w^n$.

Our first result states that $c_n$ grows asymptotically like $\mu_w^n$.

If a quasi transitive graph $G$ has infinitely many ends, and $\AUT(G)$ does not fix an end of $G$, then there exist $k\geq 1$, $a_1,a_2,\ldots,a_k> 0$ and $c>0$ such that for every $q\geq 1$ and $r=0,1,\ldots,k-1$ we have

\begin{equation}\label{eq:c_n asym}
c_{qk+r}=a_r \mu_w^{qk+r} (1+O(e^{-c q})).
\end{equation}

In particular, there exist $C_1,C_2>0$ such that

\begin{equation}\label{eq: nu 1}
C_1\mu_w^n\leq c_n\leq C_2\mu_w^n
\end{equation}

for every $n\geq 1$, and we can choose $C_1=1$ if $G$ is a transitive graph.

Our next theorem concerns the displacement of a typical self-avoiding walk of length $n$. We define $\mathbb{P}_n$ to be
the uniform measure on self-avoiding walks of length $n$ in $G$ starting from $o$, and we write $w=(w_0,w_1,\ldots,w_n)$ for a random
self-avoiding walk sampled from $\mathbb{P}_n$. We write $d_G(\cdot,\cdot)$ for the graph distance in $G$.

If $G$ has infinitely many ends, and $\AUT(G)$ does not fix an end of $G$, then there exist constants $c,t>0$ such that $\mathbb{P}_n(d_G(w_0,w_n)\geq cn)\geq 1-e^{-tn}$ for every $n\geq 1$.

It turns out that if $\AUT(G)$ fixes an end of $G$ then it is non-unimodular. To see this, let $x$ and $y$ be two vertices where $y$ lies in some small separator separating $x$ from the fixed end $\omega$, but far away from $x$. Then the size of the orbit of $y$ under $\AUT(G)_x$ is bounded by some absolute constant, but the size of the orbit of $x$ under $\AUT(G)_y$ grows as we increase the distance between $x$ and $y$.
Transitive graphs whose automorphism group admits a non-unimodular transitive subgroup were treated by Hutchcroft [32], who proved that (<ref>) and the conclusion of Theorem <ref> hold in this context. Thus we obtain the following result.

Let $G$ be a transitive graph with infinitely many ends. Then there exists constant $C>0$ such that

\[
\mu_w^n \leq c_n \leq C\mu_w^n.
\]

Moreover, there exist constants $c,t>0$ such that $\mathbb{P}_n(d_G(w_0,w_n)\geq cn)\geq 1-e^{-tn}$ for every $n\geq 1$.

§.§ Tools and proof methods

The proofs of Theorems <ref> and <ref> follow an approach similar to that of Alm and Janson in [1]. Leveraging the tree decomposition, we decompose the graph into finite or infinite
parts, and analyse the restrictions of self-avoiding walks to these parts. These restrictions give rise to the notions of configurations, shapes, and arrangements. Similar notions were also introduced in [36], but as we are working in a greater generality (in particular, parts can be infinite in our setting), some modifications in the definitions are necessary. Intuitively, each shape describes the restriction of a self-avoiding walk to a part of the tree decomposition, and each configuration describes how a self-avoiding walk crosses between two neighbouring parts. Arrangements are collections of compatible shapes and configurations, that is shapes and configurations whose partial descriptions of a self-avoiding walk fit together; see Figure <ref> for an example.

[vertex/.style=inner sep=1pt,circle,draw,fill]

ıin 0,...,9
(ı,0) – (ı,2);
ıin 0,2,...,8

ȷin 0,1

ȷin 0,...,2

[dashed] (0,ȷ)–(-.5,ȷ);
[dashed] (9,ȷ)–(9.5,ȷ);

[ultra thick,walkcol] (2,0)–(3,0)–(3,1)–(2,2)–(5,2)–(5,1)–(6,1)–(6,0)–(5,0)–(4,1);

ȷin 0,...,2
ıin 0,...,9
[vertex] at (ı,ȷ) ;

ȷin 0,...,2

ıin 1,4,7,10

ȷin 0,1

ıin 1,7

ıin 4,5,10,11

[-latex,walkcol] (0.3,0)–(0,0);
[-latex,walkcol] (0,2)–(0.3,2);
[ultra thick,walkcol,dashed] (0,0) to[bend right] (0,2);

[ultra thick,walkcol] (1,0)–(2,0);
[ultra thick,walkcol,dashed] (2,0) to[ bend right] (2,1);
[ultra thick,walkcol] (2,1)–(1,2)–(2,2);

[-latex,walkcol] (2.7,0)–(3,0);
[-latex,walkcol] (3,2)–(3.3,2);
[ultra thick,dashed,walkcol] (3,0) to[bend right] (3,1);
[ultra thick,dashed,walkcol] (3,1) to[bend left] (3,2);

[ultra thick,walkcol] (4,0)–(4,1);
[ultra thick,dashed,walkcol] (4,1) to[bend left] (4,2);
[ultra thick,walkcol] (4,2)–(5,2);
[ultra thick,dashed,walkcol] (5,2) to[bend left] (5,1);

[-latex,walkcol] (5.7,2)–(6,2);
[-latex,walkcol] (6,1)–(6.3,1);
[ultra thick,dashed,walkcol] (6,2) to[bend left] (6,1);

[ultra thick,walkcol] (7,2)–(8,2)–(8,1);
[ultra thick,dashed,walkcol] (8,1) to[bend left] (8,0);
[ultra thick,walkcol] (8,0)–(7,1);

[-latex,walkcol] (8.7,1)–(9,1);
[-latex,walkcol] (9,0)–(8.7,0);
[ultra thick,dashed,walkcol] (9,1) to[bend left] (9,0);

[ultra thick,walkcol] (10,1)–(11,1)–(11,0)–(10,0);

[-latex,walkcol] (11.7,1)–(12,1);
[-latex,walkcol] (12,0)–(11.7,0);
[ultra thick,walkcol,dashed] (12,1) to[bend right] (12,0);

[anchor=north] at (0,-.2) $c_1$;
[anchor=north] at (3,-.2) $c_2$;
[anchor=north] at (6,-.2) $c_3$;
[anchor=north] at (9,-.2) $c_4$;
[anchor=north] at (12,-.2) $c_5$;

[anchor=north] at (1.5,-.2) $s_1$;
[anchor=north] at (4.5,-.2) $s_2$;
[anchor=north] at (7.5,-.2) $s_3$;
[anchor=north] at (10.5,-.2) $s_4$;
ȷin 0,...,2
ıin 0,...,12
[vertex] at (ı,ȷ) ;

A self avoiding walk and its decomposition into configurations and shapes. Note that every edge of the graph appears in exactly one part. Dashed edges correspond to detours whose edges do not lie in this part; configurations also keep track which side the detour lies on. The little arrows pointing in and out of every configuration indicate the side on which the first and last edge of the self-avoiding walk lie, respectively.

Precise definitions are introduced in Section <ref>; for now we point out that there is a natural bijection between arrangements and self-avoiding walks and hence we may study arrangements in order to understand self-avoiding walks. We note that even though self-avoiding walks are highly non-Markovian, arrangements satisfy a spatial Markov property in the sense that compatibility of shapes and configurations is a local property; this means that in order to study arrangements, we do not have to consider their global structures, but may focus on the individual configurations and shapes. This observation is only useful for self-avoiding walks which intersect more than one part, as otherwise the self-avoiding walk is the same as its restriction to a part and we have not gained any insight. However, it turns out that the probability that a self-avoiding walk stays within one part is exponentially small – see Lemma <ref>.

The spatial Markov property of configurations gives rise to a natural recursive structure which enables us to obtain a system of equations linking the partition functions of arrangements `rooted at' given configurations.  This system can be encoded using a Jacobian matrix $\Jac(z)$, thereby reducing the problem of determining the asymptotic behaviour of self-avoiding walk to identifying which irreducible components of $\Jac(z)$ have spectral radius equal to $1$ at the critical point $z=1/\mu_w$.

We will distinguish between irreducible components rooted at I-configurations and U-configurations. Precise definitions will be given later, but intuitively, an I-configuration means that the corresponding self-avoiding walk starts and ends on different sides, and a U-configuration between two parts means that the corresponding self-avoiding walk starts and ends on the same side. For instance, configurations $c_2$ and $c_3$ in the example in Figure <ref> are I-configurations, and configurations $c_1$, $c_4$, and $c_5$ are U-configurations.

As a key step in our approach, we establish that the spectral radius of each component of U-configurations is strictly smaller than $1$ at the critical point. After developing a geometric construction that allows us to transform walks, we employ an argument in the spirit of Kesten's pattern lemma [33] to show that self-avoiding walks consisting only of U-configurations are exponentially rare. In particular, this holds for self-avoiding polygons, walks that start and end at the same vertex and are otherwise self-avoiding. The latter is known to imply that self-avoiding walk is ballistic [41], and Theorem <ref> follows.

To deduce Theorem <ref>, we establish that only one irreducible component possesses a spectral radius equal to $1$ at $z=1/\mu_w$, namely the persistent I-configurations. Leveraging the Perron-Frobenius theorem, we conclude that the spectral radius is a simple eigenvalue, allowing us to deduce that the self-avoiding walk-generating function has only simple poles. This, in turn, implies that $c_n$ grows asymptotically like $\mu_w^n$.

§.§ Paper organisation

In Section <ref> we define the model and gather some relevant definitions. In Sections <ref> and <ref> we introduce the notions of tree decompositions, configurations, and arrangements and prove some basic facts about them. In particular, we give a bijection between self-avoiding walks and certain configurations which will allow us to translate between the two objects. Next, in Section <ref> we introduce the Jacobian matrix $\Jac(z)$ and we establish the connection with the spectral radius of its irreducible components. Subsequently, in Section <ref> we show the analyticity of $\Jac(z)$ and the partition functions of U-configurations at the critical point. In Section <ref> we prove that the spectral radius of several irreducible components is strictly smaller than $1$ at the critical point. Finally, in Section <ref> we finish the proof of Theorems <ref> and <ref>.

§ DEFINITIONS AND BASIC BACKGROUND

In this section, we gather some definitions that will be used throughout the paper. Most of our notation is standard, but there is some new notation as well; we hence encourage even readers familiar with graph theory to skim this section.

§.§ Graph-theoretic definitions

A digraph $G$ consists of a set of vertices $V(G)$ and a set of arcs $E(G)$. Arcs are considered to be oriented, so every arc $e$ is assigned an initial vertex $e^- \in V(G)$ and a terminal vertex $e^+ \in V(G)$, which are different vertices of $G$; note that we allow different edges to have the same initial and terminal vertex. A graph is a digraph $G$ together with a bijection $\bar{} \; \colon E(G) \to E(G)$ such that $\bar{e}^+=e^-$, $\bar{e}^-=e^+$
and $\bar{\bar{e}}=e$. This means that arcs appear in pairs $e, \bar{e}$ having the same endpoints but different direction. We call such an unordered pair $\{e,\bar e\}$ an edge.

A digraph is called simple if it contains no arcs which are different but have the same initial and terminal vertex. In this case we sometimes abuse notation and write $e=e^-e^+$. For a vertex $v$ of $G$, we denote by $\Eout(v)$ the set of all arcs with initial vertex $v$ and by $\deg(v)=\abs{\Eout(v)}$ the degree of $v$, that is, $\deg(v)$ is the number of outgoing arcs of $v$. A digraph is called locally finite, if all vertices have finite degree.

§.§ Definition of the model

A walk in a digraph is an alternating sequence $p=(v_0,e_1,v_1, \dots, e_n,v_n)$ of vertices $v_i \in V(G)$ and arcs $e_i \in E(G)$ such that $e_{i}^-=v_{i-1}$ and $e_i^+=v_i$ for every $i \in [n]$. We point out that we cannot define a walk purely as a sequence of vertices because there may be more than one edge connecting the same pair of vertices. The length of the walk $p=(v_0,e_1,v_1, \dots, e_n,v_n)$, denoted by $\abs{p}$, is the number $n$ of arcs in $p$. Its initial vertex is $p^-=v_0$ and its terminal vertex is $p^+=v_n$. For convenience, we include in our definition the trivial walk $(v)$ of length $0$, starting (and ending) at a vertex $v$ and also the empty walk $\emptyset$ consisting of no vertices and no arcs.

A self avoiding walk (or SAW) is a walk $p$ whose vertices are pairwise different. We write $c_n(x)$ for the number of self-avoiding walks of length $n$ with initial vertex $x$, and $c_n$ for $c_n(o)$, where $o$ is some fixed root vertex in $G$. We define
\[\mu_w(x)=\limsup_{n\to \infty}c_n(x)^{1/n}.\]
We recall that on a quasi-transitive graph, the limit exists and does not depend on the base point [28]. In this case, we will simply write $\mu_w$.

A self-avoiding polygon is a walk $p=(v_0,e_1,v_1, \dots, e_n,v_n)$ with $v_0=v_n$ and with $v_i\neq v_j$ for distinct pairs $i, j$ other than
the pair $0,n$. As in [41], we identify two self-avoiding polygons which share the same set of edges. We write $p_n(x)$ for the number of self-avoiding polygons of length $n$ with initial vertex $x$. We also write $p_n$ for the number of self-avoiding polygons of length $n$ starting at the fixed root vertex $o$. We define

\[\mu_p(x)=\limsup_{n\to \infty}p_n(x)^{1/n},\]

\[\mu_p=\limsup_{n\to \infty}\left(\sup_{x\in V}p_n(x)\right)^{1/n}.\]

In certain cases, it is more convenient to work with self-avoiding walks that start at a vertex $x$ and end at a neighbour vertex of $x$. We call these walks self-avoiding returns.

§.§ Graph distance and connectedness

Let $G$ be a digraph and let $u$ and $v$ be vertices of $G$. The distance $d_G(u,v)$ from $u$ to $v$ is the length of the shortest walk with initial vertex $u$ and terminal vertex $v$. If no such walk exists, $d_G(u,v)$ is infinite. We extend this notation to subsets of $V(G)$ in the obvious way: the distance of two sets is the minimal distance between elements of these sets. We also extend this definition to arcs of $G$. For technical reasons we prefer a pair of arcs to have distance 0 if and only if the two arcs have the same set of endpoints. Thus for two arcs $e,f \in E(G)$ we define

\[
d_G(e,f) =
\begin{cases}
0 \quad &\text{if } \{e^-,e^+\} = \{f^-, f^+\} \text{ (as sets),}\\
d_G(\{e^-,e^+\},\{f^-, f^+\})+1 \quad &\text{otherwise}.
\end{cases}
\]

Observe that if $G$ is a graph, the distance is symmetric on both $V(G)$ and $E(G)$, however it is only a metric on $V(G)$ because an arc and its inverse have distance $0$.

A digraph $G$ is strongly connected if for any two vertices $u,v$ there is a walk $p$ in $G$ starting at $u$ and ending at $v$. Note that this implies that any two vertices in the digraph are connected by walks in both directions.
A strong component of $G$ is a maximal strongly connected subgraph. If $G$ is a graph, we usually omit the word “strong” in both notations.

For $K \subseteq V(G)$ we denote by $G-K$ the subgraph obtained from $G$ by removing $K$ and all arcs incident to $K$. If removing $K$ disconnects $G$, then $K$ is called a separating set. Furthermore, we denote by $G[K]$ the subgraph of $G$ induced by $K$, that is the graph $G-(V(G)\setminus K)$.

A walk is closed if its initial and terminal vertex coincide. A closed walk $p$ of length at least $3$ is called a cycle if all vertices except the initial and terminal vertex are pairwise different; note that closed walks of length $2$ are not considered cycles in this paper even though they use different arcs for both directions. A tree is a connected and cycle free graph which does not contain any cycle. A tree consisting only of vertices of degree at most 2 is called a path. We point out that unlike walks, we consider paths to be graphs and therefore a path has no `direction'; a finite path can be seen as the support of a SAW. Given two disjoint subsets $A$ and $B$ of vertices of a graph $G$, an $A$–$B$-path on $G$ is a finite path intersecting $A$ and $B$ only in its two endpoints.

§.§ Surgery on walks and multi-walks

Let $p$ be a walk. For two vertices $u$ and $v$ of $p$ we write $u p v$ for the maximal sub-walk of $p$ starting at $u$ and ending at $v$. If $u=v_0$ or $v=v_n$ we omit the corresponding vertex and denote the sub-walk by $p v$ or $u p$, respectively. We extend this notation even further. For walks $p_1, \dots, p_n$ and vertices $v_0, \dots, v_n$ in the respective walks, we denote the concatenation $(v_0 p_1 v_1)(v_1 p_2 v_2) \dots (v_{n-1} p_n v_n)$ of the sub-walks $v_{i-1} p_i v_i$ by $v_0 p_1 v_1 p_2 \dots p_n v_n$. If the terminal vertex $v$ of $p_1$ coincides with the initial vertex of $p_2$, we write $p_1p_2$ instead of $p_1vp_2$, and similarly for concatenations of multiple walks. If $e$ is an arc connecting the terminal vertex $v_1$ of $p_1$ to the initial vertex $v_2$ of $p_2$, then we write $p_1 e p_2$ instead of $p_1 v_1 (v_1,e,v_2) v_2 p_2$, and similarly for concatenations with more than two parts.

A multi-walk $p$ is a sequence of vertices and arcs obtained by stringing together the sequences of vertices and arcs corresponding to walks $p_1, \dots, p_k$; the $p_i$ are called the walk components of $p$. In other words, a multi-walk is a sequence of vertices and arcs, such that every arc in the sequence is preceded by its initial vertex and succeeded by its terminal vertex. Note that each of the walks $p_i$ is a sequence starting and ending with a vertex, so that the final vertex of $p_i$ and the initial vertex of $p_{i+1}$ will appear next to each other in the sequence $p$. In fact every appearance of two consecutive vertices in a multi-walk always marks the start of a new walk component.

§.§ Rays and ends

A ray is a one-way infinite path and a double ray is a two-way infinite path.

Two rays in a graph $G$ are called equivalent, if for every finite set $K \subseteq V(G)$ they end up in the same component of $G-K$, that is, all but finitely many of their vertices are contained in that component. An end of $G$ is an equivalence class of rays with respect to this equivalence relation. Note that for every finite set $K \subseteq V(G)$ and every end $\omega$, there is a component $H$ of $G-K$ such that all but finitely many vertices of each ray in $\omega$ are contained in $H$; in such a case we say that $\omega$ lies in $H$. Two ends $\omega_1$ and $\omega_2$ of a graph $G$ are separated by $K$ if they lie in different components of $G-K$. Halin [24] showed that an end containing arbitrarily many disjoint rays must contain an infinite family of disjoint rays, hence the maximum number of disjoint rays contained in an end $\omega$ is well defined and lies in $\N \cup \{\infty\}$. This number is called the size of the end $\omega$. An end of finite size is called thin, and an end of infinite size is called thick.

§.§ Graph automorphisms

An automorphism $\gamma$ of a graph $G$ is a permutation of $V(G)$ and $E(G)$ preserving the neighbourhood relation in $G$. More precisely, for every arc $e \in E(G)$ it satisfies $(\gamma e)^- = \gamma e^-$ and $\gamma \bar e = \overbar{\gamma e}$. The set of all automorphisms of $G$ forms a group which is called the automorphism group of $G$ and denoted by $\AUT(G)$. For a subgroup $\Gamma \subseteq \AUT(G)$ we can define an equivalence relation on $V(G)$ by $u \sim v \iff \exists \;\gamma \in \Gamma\colon u = \gamma v$. The equivalence classes with respect to this relation are called orbits, the orbit containing a vertex $v$ is denoted by $\Gamma v$. We say that $\Gamma$ acts (vertex transitively, or simply transitively, if there is exactly one orbit, and that it acts quasi-transitively, if there are only finitely many orbits. In this case the graph $G$ is also called (quasi-)transitive. Similarly, we say that $\Gamma$ acts arc transitively, if the action of $\Gamma$ on $E(G)$ has a single orbit and edge transitively, if it admits a single orbit on the set of edges. A subgraph $H$ of $G$ is called $\gamma$-invariant for $\gamma \in \AUT(G)$ if $\gamma(H)=H$.

It is well known, that if an infinite, locally finite, connected graph is quasi-transitive, then it has either one, two, or infinitely many ends. If it has one end, this end is thick. If it has two ends, both are thin and must have the same size. Finally, if it has infinitely many ends, then it must have thin ends. These and many more results were given by Halin in [25].

§.§ Open subgraphs

It will be convenient for us to consider subgraphs which are allowed to contain edges of which they do not contain both endpoints.

An open subgraph $H$ of $G$ consists of a vertex set $V(H) \subseteq V(G)$ and the set $E(H)=\{e \in E(G) \mid e^- \in V(H)\}$ of all outgoing arcs of $V(H)$ in $G$. Note that $H$ is uniquely determined by its vertex set $V(H)$; we say that $H$ is the open subgraph induced by $V(H)$. We call $H$ finite, if $V(H)$ is finite. Arcs $e \in E(H)$ such that $e^+ \in V(G) \setminus V(H)$ are called boundary arcs of $H$, and the set of all boundary arcs is denoted $\partial E(H)$. Observe that an open subgraph is a graph if and only if the set of boundary arcs is empty. The main idea behind the definition of open subgraphs is the following: for every partition of the vertex set $V(G)$, the graph $G$ is the disjoint union of the open subgraphs of $G$ induced by the sets in the partition.

An open subgraph $H$ of $G$ is called open subtree if $G[V(H)]$ is a tree and it is called open path if $G[V(H)]$ is a path. The leaves of an open subtree are the leaves of the underlying tree; in other words, when talking about the leaves of an open subtree, we ignore all boundary edges. For convenience, we let the length of an open path be the number of vertices it contains. Note that this is not the length of the underlying path—intuitively we may imagine that an open path contains an additional `half edge' in the for of an outgoing arc at each of its endpoints. An open star $S$ in $G$ is an open path of length $1$; we point out that the underlying tree of an open star is not a star, but a single vertex. It is induced by a single vertex $s$ of $G$, called the center of $S$ and we denote it by $\sta_G(s)$ or $\sta(s)$ if the graph is clear. Additionally, for an arc $e$ we write $\sta(e)$ for the open subtree with vertex set $\{e^-,e^+\}$. If $T$ is a tree, the (open) cone $K_e$ in $T$ rooted at the arc $e$ consists of $e$ and the component of $T-\{e,\bar e\}$ containing the initial vertex $e^-$ of $e$.

Let $T$ be a tree and $e,f$ be two different arcs of $T$. We call $e$ and $f$ linkable if they point away from each other, that is, they are not contained in the unique path in $T$ connecting $e^-$ and $f^-$. If $e$ and $f$ are linkable, the (unique) link $W$ connecting $e$ and $f$ is the open path induced by this path: it connects $e^-$ and $f^-$, and $e$ and $f$ are boundary arcs at the two endpoints of $W$. Observe that whenever $e$ and $f$ are linkable, the length of their link $W$ is $d_T(e,f) = d_T(e^-,f^-)+1$.

§ TREE DECOMPOSITIONS

Recall that our general proof strategy is to decompose SAWs into configurations and shapes. In order to be able to do this, we first need to decompose the graph appropriately. To this end, the goal of the current section is to show that every quasi-transitive graph with more than one end admits a tree decomposition with certain `nice properties'. We start by giving some definitions.

A tree decomposition of a graph $G$ is a pair $\Tcal=(T,\Vcal)$, consisting of a tree $T$ and a function $\Vcal: V(T) \rightarrow 2^{V(G)}$ assigning a subset of $V(G)$ to every vertex of $T$, such that the following three conditions are satisfied:

$V(G)= \bigcup_{t \in V(T)} \Vcal(t)$.

For every arc $e \in E(G)$ there is a vertex $t \in V(T)$ such that $\Vcal(t)$ contains both endpoints of $e$.

$\Vcal(s) \cap \Vcal(t) \subseteq \Vcal(r)$ for every vertex $r$ on the unique $s$–$t$-path in $T$.

For every $t \in V(t)$, the set $\Vcal(t)$ is called the part of $t$. For an arc $e=st$ of $T$, the intersection $\Vcal(e)=\Vcal(s,t):= \Vcal(s) \cap \Vcal(t)$ is called the adhesion set of $e$. Note that by definition $\Vcal(e) = \Vcal(\bar e)$.

A separation of a graph $G$ is a pair $(A,B)$ of vertex sets such that $G[A] \cup G[B]=G$, in other words $A \cup B = V(G)$, and there are no edges between $A \setminus B$ and $B \setminus A$. The intersection $A \cap B$ is called the separator, and $|A \cap B|$ is called the order of $(A,B)$. A separation $(A,B)$ of finite order is said to separate two ends $\omega_1$ and $\omega_2$ if one of them lies in a component of $B \setminus A$, and the other one lies in a component of $A \setminus B$. We say that $(A,B)$ minimally separates $\omega_1$ and $\omega_2$ if $(A,B)$ has the minimal order among all separations separating $\omega_1$ and $\omega_2$. Note that every arc $a$ of the decomposition tree $T$ corresponds to a separation of $G$ with separator $\Vcal(a)$: we call

\[\left(\bigcup_{t \in V(K_a)} \Vcal(t),\bigcup_{t \in V(K_{\bar{a}})} \Vcal(t)\right)\]

the separation of $G$ induced by $a$. Clearly, if the separation induced by $a$ is $(A,B)$, then the separation induced by $\bar a$ is $(B,A)$.

A tree decomposition $(T,\Vcal)$ of $G$ is called $\Gamma$-invariant for a group $\Gamma \leq \AUT(G)$, if every $\gamma \in \Gamma$ maps parts onto parts and thereby induces an automorphism of $T$ (which we denote by $\gamma$ as well); this clearly induces an action of $\Gamma$ on $T$.

The following result which guarantees the existence of a $\Gamma$-invariant tree decomposition is at the heart of our construction. It can be seen as a special case of <cit.>; simply note that the separations $(A,B)$ with $|A\cap B| = k$ and infinite sides $A$ and $B$ correspond to a cut system in the sense of [11], and that the $G$-tree $T(\Ccal)$ can be interpreted as a tree decomposition whose induced separations are all contained in this cut system.

Let $\Gamma$ be a group acting quasi-transitively on a locally finite graph $G$. Assume that $G$ has more than one end, and let $k$ be the minimal integer such that there are two ends which can be separated by removing $k$ vertices. Then there is a $\Gamma$-invariant tree decomposition of $G$ in which every induced separation has order $k$ and separates two ends.

Corollary <ref> below describes the tree decompositions we will be working with for the rest of this paper. It is similar to <cit.> and <cit.>. We still provide a proof for the convenience of the reader since these two results are slightly less general than ours.

We call a tree decomposition reduced if every induced separation minimally separates some pair of ends of $G$, and no two parts corresponding to adjacent vertices in $T$ coincide. We call it strongly reduced, if in addition every induced separation has order $k$, where $k$ is the minimal integer such that there is a pair of ends which can be separated by removing $k$ vertices.

In order to extract a tree decomposition with the desired properties from the above theorem, we will need the following construction. Let $\Tcal = (T,\Vcal)$ be a tree decomposition of $G$, and let $F \subseteq E(T)$ be a subset of arcs such that $\bar e \in F$ whenever $e \in F$. We define the contraction $\Tcal/F = (T/F,\Vcal/F)$ of the tree decomposition $\Tcal$ as follows.
The vertices of $T/F$ are components of $T-(E(T)\setminus F)$ with an arc between two of them if there is an arc in $T$ (which is necessarily an element of $E(T)\setminus F$) connecting the corresponding components. For a component $S\in V(T/F)$ we set $\Vcal(S) = \bigcup_{s \in V(S)} \Vcal(s)$. It is not hard to see that this defines a tree decomposition, and that the arcs of the decomposition tree are precisely the arcs in $E(T)\setminus F$. Moreover, the separations induced by an arc $e \in  E(T)\setminus F$ and its counterpart in $E(T/F)$ coincide.

Let $\Gamma$ be a group acting quasi-transitively on a locally finite graph $G$. Then there is a strongly reduced, $\Gamma$-invariant tree decomposition $(T,\Vcal)$ such that the action of $\Gamma$ on $T$ is edge transitive, but not arc transitive.

We start with the tree decomposition $\Tcal = (T, \Vcal)$ provided by Theorem <ref> and successively change it to satisfy the additional conditions.

First, let $e \in E(T)$ and let $F = E(T) \setminus (\Gamma e \cup \Gamma \bar e)$. Then $\Tcal/F$ is easily seen to be $\Gamma$-invariant, and the action of $\Gamma$ on $T/F$ is transitive on $E(T/F)$.

We claim that $\Tcal/F$ is reduced. Assume that it is not. Then there are two parts corresponding to adjacent vertices of $T/F$ which coincide. Edge transitivity implies that all parts of $\Tcal/F$ coincide, and thus all adhesion sets coincide with the parts as well. This cannot be the case since $G$ is infinite, but the adhesion sets of $\Tcal/F$ are precisely the adhesion sets of $\Tcal$ corresponding to arcs in $\Gamma e$ and thus they are finite. Finally, $\Tcal/F$ is strongly reduced due to the size of the adhesion sets in the tree decomposition $\Tcal$ provided by Theorem <ref>.

Note that if the action on $T/F$ in the above construction is not arc transitive, then we are done. Hence we may assume that we have a strongly reduced tree decomposition $\Tcal = (T, \Vcal)$ such that the action of $\Gamma$ on $T$ is arc transitive. Let $T'$ be the tree obtained by subdividing each edge in $T$ precisely once; more formally, $V(T') = V(T) \cup \{\{e,\bar e\} \mid e \in E(T)\}$, and $t \in V(T)$ and $\{e,\bar e\}$ are adjacent in $T'$ if and only if $t$ and $e$ are incident in $T$. Then it is straightforward to check that $\Tcal' = (T',\Vcal)$ defines a tree decomposition; recall that $\Vcal(st)$ is defined as $\Vcal(s) \cap \Vcal(t)$. This tree decomposition is still $\Gamma$-invariant, since the action on the tree $T$ induces an action on the tree $T'$ which takes parts to parts and adhesion sets to adhesion sets.

Next we show that $\Tcal'$ is strongly reduced. Let $st \in E(T)$. Then $|\Vcal(s)| = |\Vcal(t)|$ by arc transitivity, and consequently $|\Vcal(s)| > |\Vcal(st)|$ because otherwise the parts corresponding to $s$ and $t$ would coincide. Moreover, note that every adhesion set of $\Tcal'$ is also an adhesion set of $\Tcal$ since $\Vcal(s) \cap \Vcal(st) = \Vcal(s) \cap \Vcal(t)$. This shows that $\Tcal'$ is strongly reduced.

The action of $\Gamma$ is not transitive on the arcs of $T'$, since it is impossible to map the set $\Vcal(s)$ to the set $\Vcal(st)$ because the sets have different cardinalities. To see that the action is transitive on edges, note that by arc transitivity of the action on $T$, for any two arcs $e_1=s_1 t_1$ and $e_1=s_1 t_1$ there is $\gamma \in \Gamma$ such that $\gamma e_1 = e_2$ and thus in particular $\gamma s_1 = s_2$. We conclude that $\gamma$ maps the edge connecting $s_1$ and $\{e_1,\bar e_1\}$ to the edge connecting $s_2$ and $\{e_2,\bar e_2\}$ in $T'$.

We now collect some useful properties of the tree decompositions provided by Corollary <ref>. For the remainder of this section let $\Gamma$ be a group acting quasi-transitively on a locally finite graph $G$ and  let $\Tcal = (T,\Vcal)$ be a tree decomposition as provided by Corollary <ref>.

For every vertex $v \in V(G)$ there are only finitely many $s \in V(T)$ such that $v \in \Vcal(s)$.

Assume for a contradiction that $v$ is contained in infinitely many parts. Let $U \subseteq V(G)$ be a maximal subset such that $v \in U$ and there are infinitely many parts containing all of $U$. Note that such a maximal subset exists because if a set of vertices is contained in two parts then by <ref> it is contained in two neighbouring parts. Therefore any set of vertices which is contained in infinitely many parts must be contained in an adhesion set, and thus there is an upper bound on the size of such a set.

By <ref>, the set $\{s \in V(T)\colon U \subseteq \Vcal(s)\}$ induces a subtree $T'$ of $T$. This subtree is infinite because there are infinitely many parts containing $U$. Define $F = E(T')$ and note that $U \subseteq \Vcal(e)$ for every $e \in F$. The separation $(A_e,B_e)$ induced by $e \in F$ separates two ends, hence $v$ must have neighbours $a_e \in A_e \setminus B_e$ and $ b_e \in B_e \setminus A_e$, otherwise it would be possible to separate the ends by fewer vertices.

By <ref>, both endpoints of the arc $v a_e \in E(G)$ must be contained in some part of the tree decomposition, and since $a_e \notin B_e$ this part is $\Vcal(s)$ for some $s \in K_e$. Similarly, both endpoints of the arc $vb_e \in E(G)$ are contained in a part $\Vcal(s)$ for some $s \in K_{\bar e}$.

Since $F$ contains infinitely many arcs, there is an infinite subset $S \subseteq V(T)$ such that $\Vcal(s)$ contains a neighbour of $v$ for every $s \in S$. But $v$ only has finitely many neighbours, so infinitely many parts contain the same neighbour $u$ of $v$.

Taking an appropriate infinite subset of $F$ (either the arcs of some infinite star, or arcs on a ray which are sufficiently far apart) we can make sure that for any two vertices in $S$, the path connecting them contains at least one vertex of $T'$. By <ref> this implies that $u$ is contained in $\Vcal(s)$ for infinitely many $s \in T'$; this contradicts the maximality of $U$.

There is a constant $N$ such that $\Vcal(e) \cap \Vcal(f) = \emptyset$ whenever $e,f \in E(T)$ such that $d_T(e,f) \geq N$.

By Proposition <ref> every vertex $v \in V(G)$ is contained in only finitely many parts of the tree decomposition. Moreover $G$ is quasi-transitive, so there is a constant $N$ such that every $v \in V(G)$ is contained in at most $N$ parts. Assume that $e$ and $f$ are arcs of $T$ such that $\Vcal(e) \cap \Vcal(f)$ contains a vertex $v$ and $d_T(e,f) \geq N$. Then the unique path in $T$ connecting $e^-$ and $f^-$ has at least $N+1$ vertices. It follows from <ref> that $v \in\Vcal(t)$ for each vertex $t$ of this path, contradicting the fact that every vertex is contained in at most $N$ parts.

There is a map $\theta\colon E(G) \to V(T)$ such that for every arc $e \in E(G)$

* both endpoints of $e$ are contained in $\Vcal(\theta(e))$,

* $\theta(e) = \theta(\bar e)$, and

* $\gamma \theta(e) = \theta(\gamma e)$ for every $\gamma \in \Gamma$.

For every arc $e \in E(G)$, let $S(e) =\{s \in V(T)\colon e^-,e^+ \in \Vcal(s)\}$. The set $S(e)$ is non-empty by <ref>, the induced subgraph $T[S(e)]$ is a tree by <ref>, and this tree is finite by Proposition <ref>.

Hence it either has a central vertex, or a central edge. In the former case, we let $\theta(e)$ be the central vertex of $T[S(e)]$. In the latter case, we note that, because $\Gamma$ acts edge transitively
but not arc transitively, there is an orientation of the edges such that $\Gamma$ preserves the chosen orientations. Let $\theta(e)$ be the initial vertex of the central edge of $T[S(e)]$ with respect to this orientation.

Clearly, every $\gamma \in \Gamma$ which maps $e$ to $f$ also maps $S(e)$ to $S(f)$, and thus maps the central vertex or edge of $T[S(e)]$ to the central vertex or edge of $T[S(f)]$. Since $\gamma$ also preserves the orientation we picked above, we conclude that $\gamma \theta(e) = \theta(\gamma e)$ as desired.

Now let $\Ecal(s)=\theta^{-1}(s) \subseteq E(G)$, where $\theta$ is the function given by Proposition <ref>. Then $\Ecal(s)$ is a subset of the edge set of $G[\Vcal(s)]$.

Additionally we introduce for every arc $e=st$ of $T$ a new set of virtual arcs $\Ecal(e)=\Ecal(st)$, such that every pair of vertices of $\Vcal(e)$ is connected by an arc in $\Ecal(e)$. By definition these arcs come in pairs connecting the same vertices but having different direction, so that $\Vcal(e)$ and $\Ecal(e)$ form a complete graph. Note that the sets $\Ecal(e)$ and $\Ecal(\bar{e})$ are disjoint by definition.

We define the adhesion graph $\Gcal(e)=(\Vcal(e), \Ecal(e) \cup \Ecal(\bar{e})) (= \Gcal(\bar e)) $ and note that every pair of vertices is connected by precisely two arcs, and thus $\Gcal(e)$ is not simple unless it only consists of a single vertex.
In order to enhance readability, we usually write $\Ecal(s,t)$ instead of $\Ecal(st)$ and $\Gcal(s,t)$ instead of $\Gcal(st)$.

Finally, we assign to every vertex $s$ of $T$ the part graph

\[
\Gcal(s)=\left(\Vcal(s)\;,\; \Ecal(s) \uplus \biguplus_{e \colon e^-=s} \Ecal(e)\right).
\]

Again, $\Gcal(s)$ generally is not a simple graph since $\Ecal(s)$ and the various sets $\Ecal(s,t)$ potentially contain arcs with the same endpoints.

Recall that an open subtree $S$ of $T$ consists of a vertex set $V(S)$ and all arcs of $T$ starting at those vertices such that $T[V(S)]$ is a tree. The part graph induced by $S$ is

\[
\Gcal(S)=\left(\bigcup_{t \in V(S)} \Vcal(t)\;, \; \bigcup_{t \in V(S)} \Ecal(t) \uplus \biguplus_{e \colon \partial E(S)} \Ecal({e})\right).
\]

This is a natural extension of part graphs; it is easy to see that $\Gcal(\sta(s))=\Gcal(s)$.

For every $s \in V(T)$, the setwise stabiliser $\Gamma_{\Vcal(s)}$ acts quasi-transitively on $\Gcal(s)$.

If $u \in \Vcal(t)$ does not lie in any adhesion set, then neither does any image of $u$ under a graph automorphism. In particular, any $\gamma \in \Gamma$ mapping $u$ to some vertex $v \in \Vcal(t)$ fixes $\Vcal(t)$ and thus, under the action of the stabiliser of $\Vcal(t)$ there are only finitely many orbits of vertices in $\Vcal(t)$ not contained in any adhesion set.

Whenever $\gamma \in \Gamma$ fixes $s$ and maps a neighbour $t$ of $s$ onto some other neighbour $t'$, $\gamma$ lies in  $\Gamma_{\Vcal(t)}$ and maps the adhesion set $\Vcal(s,t)$ onto $\Vcal(s,t')$. By edge transitivity, there are at most two orbits of adhesion sets contained in $\Vcal(s)$ under the action of $\Gamma_{\Vcal(t)}$. As every adhesion set contains the same finite number of elements, $\Gamma_{\Vcal(t)}$ acts with finitely many orbits on the vertices which lie in adhesion sets of the tree decomposition.

There is $M \in \mathbb N$ such that for every $s \in V(T)$ and every $v \in \Vcal(s)$ there is a neighbour $t$ of $s$ such that $d_G(v,\Vcal(s,t)) \leq M$.

If $u$ and $v$ are vertices whose distance to the nearest adhesion set differs, then they lie in different orbits with respect to the action of $\Gamma_{\Vcal(s)}$ because $\Gamma_{\Vcal(s)}$ maps adhesion sets to adhesion sets. Hence, if the distance from a vertex to the nearest adhesion set was unbounded, then the action of $\Gamma_{\Vcal(s)}$ would have infinitely many orbits on $\Vcal(s)$, thus contradicting Proposition <ref>.

Let $e$ and $f$ be arcs of $T$. If $\Gamma$ does not fix an end of $T$, then there is an automorphism $\gamma \in \Gamma$ such that $e$ and $\gamma(f)$ are linkable.

If $e$ and $f$ lie in the same orbit, then for every odd $k$ we can choose $\gamma$ such that $d_T(e, \gamma(f)) = k$.

Since the action is transitive on edges but not on arcs, we can choose an orientation of the edges of $E$ which is preserved under the action of $\Gamma$. There are two possibilities: either every vertex has both incoming and outgoing arcs with respect to this orientation, or all arcs are oriented from one bipartite part to the other.

In the first case note that every vertex has at least two incoming and outgoing arcs (otherwise $\Gamma$ would fix an end), and hence there is $\gamma \in \Gamma$ such that $\gamma(f)^-=e^-$ and the two arcs are linked by the open path of length 1 containing only the vertex $e^-$. In the second case we can find an open path containing one or two vertices, depending on the orientations of the arcs $e$ and $f$.

If $e$ and $f$ lie in the same orbit, then we can choose $\gamma$ such that $d_T(e, \gamma(f)) = 1$. Concatenation of these open paths shows that we can also choose $\gamma$ such that $d_T(e,\gamma(f))=k$ for any odd $k$.

Let $e,f \in E(T)$. There is a family of $|\Vcal(e)|$ disjoint paths connecting $\Vcal(e)$ to $\Vcal(f)$ in $G$. Moreover, there is $N \in \mathbb N$ such that if $d_T(e,f) \geq N$, then for any pair of vertices $u \in \Vcal(e)$ and $v\in \Vcal(f)$ there is a $u$–$v$-path in $G$ which meets $\Vcal(e) \cup \Vcal(f)$ only in $u$ and $v$.

Let $(A,B)$ and $(C,D)$ be the separations induced by $e$ and $f$, respectively. It is clear from the definition of induced separations that we may without loss of generality assume that $A \cap D \subseteq \Vcal(e) \cap \Vcal(f)$. There are ends $\omega_A$ and $\omega_D$ which lie in components of $A \setminus B$ and $D \setminus C$, respectively. If there were fewer than $|\Vcal(e)|$ disjoint paths connecting $\Vcal(e)$ to $\Vcal(f)$ in $G$, then by Menger's theorem it would be possible to separate these two ends by removing fewer than $|\Vcal(e)|$ vertices; this contradicts the fact that the tree decomposition is strongly reduced.

For the `moreover' part, let $e' \in E(T)$, and let $H$ be a finite connected subgraph of $G$ containing all vertices in $\Vcal(e')$. By Corollary <ref> there is some $N' \in \mathbb N$ such that $\Vcal(f') \cap V(H) = \emptyset$ whenever the distance between $e'$ and $f'$ in $T$ is at least $N'$.

Now assume that the distance between $e$ and $f$ is at least $N=2N'$, and let $e'$ be an arc lying in the center of the path connecting $e$ and $f$ in $T$. The union of $H$ and the collection of disjoint paths from the first part is a connected subgraph of $G$ because each of the paths must pass through a vertex in $\Vcal(e')$. Vertices in $\Vcal(e) \cup \Vcal(f)$ have degree $1$ in this graph because of the choice of $N$. Hence they cannot appear as internal vertices of any path, and thus any path in this subgraph meets $\Vcal(e) \cup \Vcal(f)$ at most in its endpoints. Since the graph is connected, it contains the desired paths.

§ CONFIGURATIONS AND ARRANGEMENTS

The goal of this section is to utilize tree decompositions to build SAWs from so-called shapes living on the graphs $\Gcal (t)$ for $t \in V(T)$ and configurations living on  $\Gcal (e)$ for $e \in E(T)$ where $\Tcal=(T,\Vcal)$ is a tree decomposition of a quasi-transitive graph $G$; usually the one provided by Corollary <ref>. In the case where $G$ is a one-dimensional lattice, this was already done by Alm and Janson [1]. Here we use a more general approach similar to the one introduced in [36] for tree decompositions whose parts are finite. As we also want to treat infinite parts, our definitions and notation are slightly different from the ones used there.

Let $G$ be connected, locally finite, simple and quasi-transitive, and let $\Tcal=(T,\Vcal)$ be a tree decomposition of $G$. Assume that we have a map $\theta$ mapping each edge to a part containing its endpoints as in Proposition <ref>. Define adhesion graphs and part graphs for this tree decomposition in the same way as we did after  Proposition <ref> for the tree decomposition provided by Corollary <ref>.  A configuration on an arc $e$ of $T$ with respect to $\Tcal$ is a triple $c=(q,x,y)$, where $x,y \in \{e,\bar{e}\}$ are not necessarily different orientations of $e$, and $q$ is either a SAW on the graph $\Gcal(e)$ or equal to the empty set $\emptyset$. In the latter case $c$ is called the empty configuration.

We call $x$ the entry direction and $y$ the exit direction of $c$. The inverse of the configuration $c=(q,x,y)$ is the configuration $\bar c=(\bar q ,y,x)$ consisting of the reverse walk $\bar q$ of $q$, and which has entry direction $y$ and exit direction $x$.

A shape on a vertex $s$ of $T$ with respect to $\Tcal$ is a SAW $p$ on the part graph $\Gcal(s)$. We say that a shape $p$ on $s$ and a configuration $(q,x,y)$ on an arc $e \in \Eout(s)$ are compatible if the following three conditions hold; the intersection of a walk $p$ with a subgraph is defined as the subsequence of $p$ consisting of the vertices and edges contained in that subgraph and therefore this intersection is in general not a walk but a multi-walk.

$p \cap \Gcal(e) = q \cap \Gcal(s)$.

If $x=e$, then $p$ starts in $\Vcal(e)$.

If $y=e$, then $p$ ends in $\Vcal(e)$.

An arrangement on a finite open subtree $S$ of $T$ with respect to $\Tcal$ is a pair $A=(P,C)$ of maps assigning to every vertex $s \in V(S)$ a shape $P(s)$ and to every arc $e$ in $E(S)$ a configuration $C(e)=(Q(e),X(e),Y(e))=C(\bar e)$, where $X(e), Y(e)$ may be arcs in $E(S)$ or their inverses, such that for $s \in V(S)$ the following conditions hold:

$P(s)$ and $C(e)$ are compatible for every $e \in \Eout(s)$.

There is at most one arc $e\in \Eout(s)$ such that $X(e) = e$. If there is no such arc, then $P(s)$ starts with a non-virtual arc.

There is at most one arc $e\in \Eout(s)$ such that $Y(e) = e$. If there is no such arc, then $P(s)$ ends with a non-virtual arc.

The weight $\norm{A}$ of the arrangement $A=(P,C)$ on the open subtree $S$ is the total number of non-virtual arcs contained in all the walks $P(s)$ for $s \in V(S)$, so $\norm{A}=\sum_{s \in V(S)} \norm{P(s)}$, where $\norm{P(s)}$ denotes the number of non-virtual arcs in $P(s)$.

The arrangement $A$ is called boring on an arc $e \in E(S)$ if $X(e)=Y(e)$ and all arcs of $Q(e)$ are contained in $\Ecal(X(e))$; in this case we also say that the configuration $C(e)=(Q(e),X(e),Y(e))$ is boring. Intuitively, if an arrangement is boring on an arc $e$, then this means that all non-trivial shapes lie on one side of this arc; in other words we won't lose any information by removing everything that lies on the other side of this arc from the open subtree. We can thus reduce an arrangement by iteratively pruning subtrees attached to edges on which the arrangement is boring until all such subtrees are trivial. We call an arrangement $A$ reduced if it is non-boring on all arcs in $E(S)\setminus \partial E(S)$. Call a reduced arrangement complete if the configuration $C(e)$ is boring and $X(e)= \bar e$ for every $e \in  \partial E(S)$.

Our goal is to establish a relation between (complete) arrangements on finite open subtrees $S$ of $T$ and self-avoiding walks of length at least 1 on $\Gcal(S)$. While our definition of arrangements differs slightly from the definitions of configurations in [36], we will follow the same strategy, thus our proofs are quite similar.

The main result of this section is Theorem <ref> which intuitively states that every self avoiding walk has an arrangement associated to it and (subject to some technical conditions) this is a bijection. The technical details are quite messy, hence we start by providing a very rough sketch of the main ideas for the convenience of the reader. Tree decompositions can be made coarser by contracting edges, and finer by decontracting these edges again, and we can define corresponding operations on arrangements; see Figure <ref> for a sketch and Constructions <ref> and <ref> for details. Every self-avoiding walk $p$ consists of finitely many edges. Thus after some finite number of contractions in the tree decomposition, all edges of $p$ are contained in one part. Hence $p$ is a shape on this part, and this shape can be extended to a configuration on the open star. Decontracting this arrangement gives the arrangement on the original tree decomposition corresponding to $p$. We may also perform these steps in reverse order to translate an arrangement into a self-avoiding walk.

In the remainder of this section we provide the details to the above proof sketch. As a first step, we show that a self avoiding walk whose edges belong to a single part can indeed be transformed into an arrangement on the open star.

Let $S=\sta(s)$ be an open star in $T$ and $p$ be a shape on $s$.

There is an arrangement $A=(P,C)$ on $S$ such that $P(s)=p$.

For $e \in E(S)$ the walk $Q(e)$ of the configuration $C(e)$ is uniquely defined by $p$.

If $p$ starts in $\Vcal(f)$ for some $f \in E(S)$ and/or ends in $\Vcal(f')$ for some $f' \in E(S)$, we may choose $A$ such that $X(f)=f$ and/or $Y(f')=f'$ holds, respectively.

Let $e \in E(S)$. Our first goal is to construct a walk $q$ on $\Gcal(e)$ such that <ref> is satisfied and show that this walk is unique. If $p \cap \Gcal(e) =\emptyset$, we set $q=\emptyset$ the empty walk. Otherwise  $p \cap \Gcal(e)$ is a multi-walk, let $p_1, \dots, p_n$ be its walk-components. Set $q=p_1 e_1 p_2 \dots e_{n-1} p_n$, where $e_i \in \Ecal(\bar e)$ connects $p_i^+$ and $p_{i+1}^-$. It is not hard to check that <ref> is satisfied. Furthermore, by definition $\Vcal(e) \subseteq V(\Gcal(s))$ and $\Ecal(e) \subseteq E(\Gcal(s))$ holds, thus there is no other way to complete $q$.

Let now $P(s)=p$ and for $e \in E(S)$ write $Q(e)$ for the walk $q$ on $G(e)$ constructed above. If $P(s)$ starts in some adhesion set $\Vcal(f)$, we may choose $X(f)=f$ and $X(e)=\bar e$ for $e \in E(S)\setminus\{f\}$. Otherwise $P(s)$ starts with a non-virtual arc and we have to choose $X(e)=\bar e$ for every $e \in E(S)$. Similarly, if $P(s)$ ends in some adhesion set $\Vcal(f)$ we may choose $Y(f)=f$ and $X(e)=\bar e$ for $e \in E(S)\setminus\{f\}$, otherwise we have to choose $X(e)=\bar e$ for every $e \in E(S)$. In any case this construction satisfies <ref> – <ref>.

The following Lemma formalises the intuition behind the notion of boring configurations. In particular, it shows that it is usually sufficient to work with reduced arrangements, as any non-reduced arrangement can be restricted to a smaller open subtree without losing any information.

Let $S=\sta(s)$ be an open star in $T$, let $e \in E(S)$ be one of its arcs and let $c=(q,x,y)$ be a non-empty boring configuration on $e$ such that $x=y=e$. Then there is a unique arrangement $A=(P,C)$ on $S$ such that $C(e)=c$. Additionally, $P(s)$ contains no non-virtual arcs and $C(f)$ is boring for every $f \in E(S)\setminus \{e\}$.

By definition of boring configurations the walk $q$ contains only arcs in $\Ecal(e)$ and no arcs in $\Ecal(\bar e)$. Thus $q$ is a shape on $s$ and Lemma <ref> provides the existence of an arrangement $A=(P,C)$ on $S$ such that $P(s)=q$. Additionally $q$ starts and ends in $\Vcal(e)$, so we may choose $A$ such that $X(e)=Y(e)=e$. Note that this is the only way of choosing entry and exit directions which is consistent with the given boring configuration $c$, and it is easy to check that indeed $C(e)=c$.

Let $f \neq e$ be an arc of $S$. Then properties <ref> and <ref> imply $X(f)=Y(f)=\bar f$ because $X(e)=Y(e) = e$. Also $P(s) \cap \Gcal(f)$ consists only of vertices, so <ref> implies that all arcs of $Q(f)$ are contained in $\Ecal(\bar f)$, so that $C(f)$ is boring.

Observe that for any arrangement $A=(P,C)$ on a finite open subtree $S$ of $T$ empty configurations can only occur on boundary arcs of $S$. This follows from the fact that if $X(e) = e$ for some interior arc $e$ of $S$, then the walk $P(e^-)$ has to start in $\Vcal(e)$ by <ref> and thus $Q(e)$ is not empty by <ref>.

In the next step we will construct coarser tree decompositions from a given tree decomposition $\Tcal=(T,\Vcal)$ of $G$ by contracting arcs of $T$ (similar to the construction used in the proof of Corollary <ref>).

We first recall the definition of contraction in the special case where only a single edge is contracted, and introduce some additional notation for this special case. Let $f$ be an arc of $T$. The tree decomposition $\Tcal/f=(T/f,\Vcal/f)$ of $G$ obtained from $\Tcal$ by contracting $f$ is given as follows. The vertex set $V(T/f)$ of the decomposition tree $T/f$ is obtained from $V(T)$ by replacing $f^-$ and $f^+$ by a single new vertex $s_f$ and its edge set $E(T/f)$ is obtained from $E(T)$ by deleting $f$ and $\bar{f}$ and for the remaining edges changing all endpoints in $\{f^-, f^+\}$ to the new vertex $s_f$. In other words, we contract $f$ and leave the names of vertices and edges unchanged wherever possible. Furthermore, the part corresponding to $s_f$ is $\Vcal/f(s_f)=\Vcal(f^-) \cup \Vcal(f^+)$, for all other vertices $t \in V(T/f)$ we define $\Vcal/f(t) = \Vcal(t)$. It is not hard to check that the result satisfies properties <ref> – <ref>, thus being a tree decomposition. The part graph of the new vertex is $\Gcal(s_f)=\Gcal(\sta(f))$, all other part graphs and adhesion graphs are inherited from $\Tcal$ and stay the same.

[scale=1.2,vertex/.style=inner sep=1pt,circle,draw,fill,use Hobby shortcut]

(30:1) arc(30:330:1cm)
(90:1) arc(-30:-90:1cm)
(-90:1) arc(30:90:1cm);

[shift = (120:.7), rotate = 120]
(30:1) arc(30:-30:1cm) arc(210:150:1cm);

[shift = (-120:.7), rotate = -120]
(30:1) arc(30:-30:1cm) arc(210:150:1cm);

(30:1) arc(30:330:1cm)
(90:1) arc(-30:-90:1cm)
(-90:1) arc(30:90:1cm);

[shift = (120:.7), rotate = 120]
(30:1) arc(30:-30:1cm) arc(210:150:1cm);

[shift = (-120:.7), rotate = -120]
(30:1) arc(30:-30:1cm) arc(210:150:1cm);

[thick] (90:.5) to [bend right] (-130:.9);
[thick,densely dotted] (-130:.9)–(-110:.9);
[shift = (-120:.7),thick,densely dotted] (-130:.9)–(-110:.9);
[thick] (-110:.9) to [bend left=37] (10:.9);
[thick] (-10:.9) to[bend right=27] (-110:.9);
[thick,densely dotted] (-130:.9)–(-110:.9);
[shift = (-120:.7),thick,densely dotted] (-130:.9)–(-110:.9);
[thick] (-130:.9) to [bend left=27] (10:.9);

[thick] (-10:.9) to [bend right=20] (-80:.5);

[yshift=-.8cm] at (-30:1) $\Gcal(s_f)$;

(0:1) arc(0:360:1cm)
(90:1) arc(-30:-90:1cm)
(-90:1) arc(30:90:1cm)
(30:1) arc(150:210:1cm);

[shift = (0:.7)]
(30:1) arc(30:-30:1cm) arc(210:150:1cm);

[shift = (120:.7), rotate = 120]
(30:1) arc(30:-30:1cm) arc(210:150:1cm);

[shift = (-120:.7), rotate = -120]
(30:1) arc(30:-30:1cm) arc(210:150:1cm);

[thick] (90:.5) to [bend right] (-130:.9);
[thick,densely dotted] (-130:.9)–(-110:.9);
[shift = (-120:.7),thick,densely dotted] (-130:.9)–(-110:.9);
[thick] (-110:.9) to [bend left=37] (10:.9);
[thick,densely dotted] (10:.9)–(-10:.9);
[shift = (0:.68),thick,densely dotted] (10:.9)–(-10:.9);
[thick] (-10:.9) to [bend right=20] (-80:.5);

[xshift=1.4cm, shift = (30:1), shift = (-30:1),rotate=180]
(0:1) arc(0:360:1cm)
(90:1) arc(-30:-90:1cm)
(-90:1) arc(30:90:1cm)
(30:1) arc(150:210:1cm);

[shift = (120:.7), rotate = 120]
(30:1) arc(30:-30:1cm) arc(210:150:1cm);

[shift = (-120:.7), rotate = -120]
(30:1) arc(30:-30:1cm) arc(210:150:1cm);

[thick] (-10:.9) to[bend right=27] (-110:.9);
[thick,densely dotted] (-130:.9)–(-110:.9);
[shift = (-120:.7),thick,densely dotted] (-130:.9)–(-110:.9);
[thick] (-130:.9) to [bend left=27] (10:.9);

[anchor=north] at (-70:1) $\Gcal(f^-)$;
[anchor=north,xshift=2cm,shift=(30:1),shift=(-30:1)] at (-110:1) $\Gcal(f^+)$;
[anchor=north,xshift=1cm,shift=(-30:1)] at (0,-.1) $\Gcal(f)$;

[-Latex] (-3.5,.2)–(-1.5,.2);
[Latex-] (-3.5,-.2)–(-1.5,-.2);
[anchor=south] at (-2.5,.25) Contraction;
[anchor=north] at (-2.5,-.25) Projection;

Sketch of contraction (see Construction <ref>) and projection (see Construction <ref>) of arrangements with respect to the arc $f$.

Given an arrangement with respect to the tree decomposition $\Tcal$, we can define the contraction of the arrangement as described below. The construction and its inverse (Construction <ref>) are sketched in Figure <ref>.

Let $A=(P,C)$ be an arrangement on the open subtree $\sta(f)$ of $T$ and let $\sta(s_f)$ be the open star in $T/f$ centered in the new vertex $s_f$ introduced by contracting $f$ in $T$. We construct a pair $(P/f,C/f)$ and show that it is an arrangement on $\sta(s_f)$. Configurations stay the same; we set $C/f(e)=C(e)$ for every $e \in \Eout(s_f)$. By Remark <ref> the configuration $C(f)$ is non-empty, let $Q(f)=(v_1, e_1, \dots, e_{k-1}, v_k)$. By <ref> we have that $P(f^-)$ and $P(f^+)$ both visit $v_1, \dots, v_k$ in this order and no other vertices of $\Vcal(f)$. Let $a_0=X(f)$, let $a_k=Y(f)$ and for $j \in [k-1]$ let $a_j \in \{f,\bar{f}\}$ such that $e_j \in \Ecal(a_j)$.
We define the walk $P/f(s_f)$ as the concatenation

\[
P(a_0^+)v_1P(a_1^+)v_2\dots v_kP(a_k^+).
\]

In other words, $P/f(s_f)$ is obtained from $P(f^-)$ and $P(f^+)$ by deleting all arcs in $\Ecal(f)$ and then piecing the walk components of the resulting multi-walks together in a consistent manner.

Intuitively it should be clear that applying Construction <ref> to an arrangement yields an arrangement on the contracted tree decomposition. We will now prove this formally.

The walk $P/f(s_f)$ is a self-avoiding walk on $\Gcal(s_f)$ satisfying $ P/f(s_f) \cap \Gcal(f^-) = P(f^-)  - \Ecal(f)$ and $P/f(s_f) \cap \Gcal(f^+) = P(f^+)  - \Ecal(\bar f)$. In particular, the set of arcs contained in $P/f(s_f)$ consists of the arc sets of $P(f^-)  - \Ecal(f)$ and $P(f^+)  - \Ecal(\bar f)$.

Let  $P/f(s_f) = P(a_0^+)v_1P(a_1^+)v_2\dots v_kP(a_k^+)$ as defined above. If one of $P(f^-)$ and $P(f^+)$ is the empty walk, then all claimed properties are trivially satisfied, so we may assume that both walks are non-empty. By <ref>, $P(X(f)^-)$ must start in $v_1$ and by <ref>, $P(Y(f)^-)$ must end in $v_k$, so both $P(a_0^-)v_1$ and $v_kP(a_k^-)$ are trivial. By definition $Q(f)$ is a walk consisting of arcs $e_1, \dots e_{k-1}$ and by <ref>, $v_jP(a_j^-)v_{j+1}$ consists only of the virtual arc $e_j$. Combining these observations with the fact that $P(f^-)$ can be decomposed as $P(f^-) = P(f^-)v_1P(f^-)v_2\dots v_l P(f^-)$
we conclude that

\[P/f(s_f) \cap \Gcal(f^-) = P(f^-)  - \Ecal(f),\]
and similarly for $f^+$. This implies that $P/f(s_f)$ uses no vertex more than once: for vertices in $\Vcal(f)$, this holds by definition, for vertices outside of $\Vcal(f)$, this follows from the fact that $P(f^-)$ and $P(f^+)$ are self-avoiding. Hence $P/f(s_f)$ is self-avoiding.

The pair $A/f=(P/f,C/f)$ defined in Construction <ref> is an arrangement on $\sta(s_f)$.

We have already seen that $P/f(s_f)$ is a shape and by definition $C/f(e)=C(e)$ is a configuration, so we only need to verify <ref> – <ref>. Let $e \in \sta(s_f)$ and assume without loss of generality that $e^-=f^-$ in $T$. Then by construction

\[
P/f(s_f) \cap \Gcal(e) = P(f^-) \cap \Gcal(e) = Q(e) \cap \Gcal(f^-)=Q(e) \cap \Gcal(s_f),
\]

so <ref> holds. Furthermore $X(e)=e$ if and only if $P(f^-)$ starts in $\Vcal(e)$ and additionally $X(f)=\bar f$ by <ref> and thus $P(f^+)$ starts in $\Vcal(f)$. Then by construction the starting vertices of $P/f(s_f)$ and $P(f^-)$ coincide, so $P/f(s_f)$ starts in $\Vcal(e)$ and <ref> is satisfied. Finally either $X(f)=f$ or $X(f)=\bar{f}$, so again by <ref> at most one arc $e \in \sta(s_f)$ can satisfy $X(e) = e$. If there is no such arc, then each $e \in \Eout(X(f)^-)$ satisfies $X(e)=\bar e$, so $P(X(f)^-)$ starts with a non-virtual arc, so $P/f(s_f)$ starts with a non-virtual arc and <ref> follows. Finally <ref> and <ref> follow analogously by considering exit directions.

We have managed to contract an arrangement on the open tree $\sta(f)$ of $T$ to obtain an arrangement on the open star $\sta(s_f)$ of $T/f$. In the next step, we want to do the converse, projecting a given arrangement $A=(P,C)$ on $\sta(s_f)$ down to obtain an arrangement $\pi A=(\pi P, \pi C)$ on $\sta(f)$, see again Figure <ref> for a sketch. For technical reasons we assume that $P(s_f)$ meets $\Vcal(f)$.

As one might expect, we choose $\pi C(e)=C(e)$ for $e \in \partial \Eout(f)$.
By definition $P(s_f) \cap \Gcal(f)$ is a multi-walk on the adhesion graph $\Gcal(f)$. Each of its walk components consists only of a single vertex $v_i$. Therefore the walk $P(s_f)$ can be written as a concatenation $q_0 \dots q_k$ of sub-walks $q_i$, where $q_0=P(s_f) v_1$, $q_k=v_k P(s_f)$ and $q_j=v_j P(s_f) v_{j+1}$ for $j \in [k-1]$. Note that while $q_0$ and $q_k$ may be trivial, all other $q_j$ must have length at least 1. By the basic properties of tree-decompositions, the arcs of each (non-trivial) $q_j$ are contained in exactly one of $\Gcal(f^-), \Gcal(f^+)$. Let $a_j \in \{f,\bar f\}$ be such that $q_j \in \Gcal(a_j^+)$; in other words, $a_j$ marks on which side of $f$ the part containing $q_j$ lies. For $j \in [k-1]$ let $e_j$ be the (virtual) arc in $\Ecal(a_j)$ connecting $v_j$ and $v_{j+1}$. We are able to construct shapes $\pi P(s)$ for $s \in \{f^-, f^+\}$ and a configuration $\pi C(f)=(\pi Q(f), \pi X(f),\pi Y(f))=\pi C(\bar f)$. The shape $\pi P(s)$ is given as the concatenation $p_0 p_1 \dots p_k$, where

\[
q_j \quad &\text{if }  a_j^+=s \\
(v_j, e_j, v_{j+1}) \quad &\text{if } j \in [k-1] \text{ and } a_j^+\neq s \\
(v_j) \quad &\text{if } j \in \{0,k\} \text{ and } a_j^+\neq s.
\end{cases}
\]

The walk $\pi Q(f)$ is given as $\pi Q(f)=(v_1, e_1, v_2, \dots, e_{k-1}, v_k)$. Finally, by <ref> there is at most one $e \in \Eout(s_f)$ such that $X(e) = e$. If such an arc exists, we choose $\pi X(f)\in \{f, \bar f\}$ such that $\pi X(f)^+=e^-$. Otherwise $P(s_f)$ starts with a non-virtual arc $e_0 \in \Ecal(s_f)$ and we choose $\pi X(f)\in \{f, \bar f\}$ such that $e_0 \in \Ecal(\pi X(f)^+)$. Similarly if there is an arc $e \in \Eout(s_f)$ such that $Y(e) = e$ we choose $\pi Y(f)$ such that $\pi Y(f)^+=e^-$, otherwise we choose $Y(f)$ such that the last arc of $P(s_f)$ is contained in $\Ecal(\pi Y(f)^+)$.

We no prove that applying Construction <ref> to an arrangement gives an arrangement.

The walks $\pi P(f^-)$ and $\pi P(f^+)$ are self-avoiding walks on $\Gcal(f^-)$ and $\Gcal(f^+)$ satisfying $P(s_f) \cap \Gcal(f^-) = \pi P(f^-) - \Ecal(f)$ and $P(s_f) \cap \Gcal(f^+) = \pi P(f^+) - \Ecal(\bar f)$.

By construction $\pi P(f^-)$ consists of all walk-components $q_j$ of $P(s_f)$ contained in $\Gcal(f^-)$, while those $q_j$ not contained in $\Gcal(f^-)$ are replaced by virtual arcs $e_j \in \Ecal(f)$ (shortcuts) connecting the same endpoints. In particular $\pi P(f^-)$ is a walk and $P(s_f) \cap \Gcal(f^-) = \pi P(f^-) - \Ecal(f)$. Furthermore it is self-avoiding because its sequence of vertices also occurs in the SAW $P(s_f)$. The statements for $\pi P(f^+)$ follow analogously.

The map $\pi A=(\pi P,\pi C)$ defined in Construction <ref> is an arrangement on $\sta(f)$.

We show that <ref> – <ref> holds for $s=f^-$, the other vertex $f^+$ is treated analogously. For $e \in \Eout(f^-) \setminus\{f\}$ compatibility follows from the fact that $\pi P(f^-) \cap \Gcal(e)=P(s_f) \cap \Gcal(e)$ and

\[
\pi X(e)= e \iff X(e)= e \iff P(s_f) \text{ starts in } \Vcal(e) \iff \pi P(f^-) \text{ starts in } \Vcal(e).
\]

and the analogue statement for $\pi Y(e)$. We still need to consider the arc $f$. By construction $\pi Q(f) \cap \Gcal(f^-)$ is a non-empty multi-walk consisting of all virtual arcs $e_j$ in $\Ecal(f)$ such that $q_j \in \Gcal(f^+)$, which are exactly the virtual arcs in $\pi P(f^-) \cap \Gcal(f)$. Furthermore $\pi X(f)=f$ holds either if $X(e)=e$ holds for some arc $e \in \Ecal(f^+) \setminus \{\bar f\}$ or if $q_0$ is non-trivial and contained in $\Gcal(f^+)$. In both cases $\pi P(f^-)$ starts at $v_0 \in \Vcal(f)$. Similarly, if $\pi Y(f) = f$, then $\pi P(f^-)$ ends at $v_k \in \Vcal(f)$, so <ref> is satisfied. Again by construction $\pi X(f)= f$ can only hold if $\pi X(e)=\bar e$ for all $e \in \Ecal(f^-) \setminus \{\bar f\}$, so at most one  $e \in \Ecal(f^-)$ satisfies $\pi X(e) \neq e$. If there is no such arc, then $P(s_f)$ starts with a non-virtual arc which is by construction contained in $\Gcal(f^-)$. In particular $\pi P(f^-)$ starts with a non-virtual arc, yielding <ref>. Similar arguments for the exit direction $\pi Y$ yield <ref>. We conclude that $\pi A$ is indeed an arrangement on $\sta(f)$.

Next we show that contraction and projection are inverses of one another. The technical condition that the shape meets $\Vcal(f)$ ensures that all shapes are non-empty. This is crucial for the bijection between self-avoiding walks and arrangements. Without this technical condition, every self-avoiding walk would correspond to not just one, but infinitely many different arrangements, obtained by attaching arbitrarily many boring configurations and suitable (often empty) shapes.

Contraction of arrangements $A \mapsto A/f$ defines a bijection between arrangements on the open subtree $\sta(f)$ of $T$ with respect to $\Tcal$ and arrangements on the open star $\sta(s_f)$ centered in the contracted vertex $s_f$ of $T/f$ with respect to $\Tcal/f$ whose shape on $s_f$ meets $\Vcal(f)$. Its inverse map is the projection $A \mapsto \pi A$ of arrangements. Moreover $\norm{A}= \norm{A/f}$ holds.

We have already seen that $A \mapsto A/f$ maps arrangements on $\sta(f)$ to arrangements on $\sta(s_f)$ and that $A \mapsto \pi A$ maps arrangements on $\sta(s_f)$ to arrangements on $\sta(f)$. By Remark <ref> the walk $Q(f)$ of the configuration $C(f)$ is non-empty, so by construction $P/f(s_f)$ intersects $\Vcal(f)$. Furthermore by Lemma <ref> the set of non-virtual arcs of $P/f(s_f)$ is the disjoint union of the sets of non-virtual arcs of $P(f^-)$ and $P(f^+)$, so $\norm{A}= \norm{A/f}$ holds.

Let $A$ be an arrangement on $\sta(f)$. We claim that $\pi(A/f)=A$.
By construction $\pi(A/f)$ is an arrangement on $\sta(f)$ such that $\pi (C/f)(e) = C/f(e)=C(e)$ for every $e \in \Eout(f)$. Additionally, by Lemmas <ref> and <ref> we have that $\pi(P/f)(f^-)$ satisfies

\[
\pi (P/f)(f^-)-\Ecal(f)=P/f(s_f)\cap \Gcal(f^-)=P(f^-)-\Ecal(f).
\]

Any virtual arcs of $\pi P/f(f^-)$ in $\Ecal(f)$ must connect the walk-components of $\pi P/f(f^-)-\Ecal(f)$, thus we conclude $\pi (P/f)(f^-)=P(f^-)$. In a similar way we obtain $\pi (P/f)(f^+)=P(f^+)$.

It remains to show that $\pi(C/f)(f)=C(f)$. Equality of the walks $\pi (Q/f)(f)$ and $Q(f)$ follows directly from <ref> of compatibility: Both walks $\pi (Q/f)(f)$ and $Q(f)$ consist of all virtual arcs of the shapes $\pi (P/f)(f^-)=P(f^-)$ and $\pi (P/f)(f^+)=P(f^+)$ contained in $\Gcal(f)$ and also the order of these arcs coincide. Finally, if there is some arc $e \in \partial \Eout(f)$ such that $X(e)= e$, then also $\pi (X/f)(e) = e$ and thus <ref> yields $X(f)= \pi (X/f)(f)$. Otherwise $X(e)=\bar e$ holds for all $e \in \Eout(X(f)^+)$, so by <ref> the walk $P(X(f)^+)$ starts with a non-virtual arc $e_0$ and by <ref> the walk $P(X(f)^-)$ starts in $\Vcal(f)$. In particular, the first arc of $P/f(s_f)$ is $e_0$ and by construction $\pi (X/f)(f)=X(f)$. Analogous arguments yield $\pi (Y/f)(f)=Y(f)$.

The proof that $(\pi A)/f=A$ holds for every arrangement $A=(P,C)$ on $\sta(s_f)$ such that $P(s_f)$ intersects $\Vcal(e)$ works similarly and is left to the reader.

Let $S$ be a finite open sub-tree of $T$. Starting with a given tree decomposition $\Tcal=(T,\Vcal)$ of $G$ the process of edge contraction can be iteratively applied to contract each interior edge of $S$. In this way $S$ is contracted into an open star centered at a single vertex $s_S$. We denote the obtained tree decomposition by $\Tcal/S=(T/S,\Vcal/S)$. As before, an arrangement $A$ on $S$ will be contracted to an arrangement $A/S$ on the open star $\sta(s_S)$ of $T/S$.

It is not hard to see that neither the contracted tree decomposition $\Tcal/S=(T/S, \Vcal/S)$ nor the contracted arrangement $A/S=(P/S,C/S)$ on $\sta(s_S)$ depends on the order of edge contractions: Clearly the tree obtained by consecutive edge contractions does not depend on the order. Additionally $\Vcal/S(s_S)$ is the union of all vertices in $\Vcal(s)$ for $s \in V(S)$ and $\Vcal/S(t)=\Vcal(t)$ for $t \in V(T/S)\setminus \{s_S\}$. In particular $\Tcal/S$ does not depend on the order of contractions of internal edge in $S$.

The configurations on boundary arcs remain the same after each step of contraction of $A$, so in particular $C/S(e)=C(e)$ holds for any arc $e \in \Eout(s_S)=\partial E(S)$. Additionally, by Lemma <ref> the walk $P(s_S)$ consists of all non-virtual arcs of walks $P(s)$ for $s \in V(S)$ and its direction is uniquely defined. Again, this representation of $A/S$ on $S$ does not depend on the order of contractions of edges in $S$.

We immediately obtain the following corollary of Proposition <ref>.

Let $S$ be an open subtree of $T$. The contraction of arrangements $A \mapsto A/S$ defines a bijection between arrangements on $S$ with respect to $\Tcal$ and arrangements on the open star $\sta(s_S)$ centered in the contracted vertex $s_S$ of $T/S$ with respect to $\Tcal/S$ whose shape on $s_S$ meets $\Vcal(s)$ for every $s \in V(S)$.
Moreover $\norm{A}= \norm{A/S}$ holds.

Corollary <ref> can be used to define a map $\varphi$ translating any arrangement $A$ on an open subtree $S$ of $T$ to the self-avoiding walk $\varphi(A)=P/S(s_S)$ on the graph $\Gcal(S)$. Observe that by definition the length of $\varphi(A)$ is $\norm{A}$. We call $\varphi(A)$ the walk represented by $A$ and $A$ a representation of $\varphi(A)$. Theorem <ref> below shows that every SAW has some representation.

Let $S$ be a not necessarily finite subtree of $T$ and $w$ be a SAW on $\Gcal(S)$. The support of $w$ in $T$ is the smallest open subtree $S'$ of $S$ such that all arcs of $w$ are contained in $\Gcal(S)$.

Let $T'$ be an open subtree of $T$ and let $w$ be a SAW on $\Gcal(T')$. Then there is an arrangement $A=(P,C)$ on the support of $w$ in $T$ representing $w$. Moreover, if $w$ starts in $\Vcal(f)$ for some $f \in \partial E(T')$ and/or ends in $\Vcal(f')$ for some $f' \in \partial E(T')$, we may choose $A$ such that $X(f)=f$ and/or $Y(f')=f'$ holds, respectively.

Let $S$ be the support of $w$ in $T$. By definition $w$ is a shape on the contracted vertex $s_{S}$ of $T/S$, thus Lemma <ref> <ref> provides us with an arrangement $A'=(P',C')$ on $\sta_{T/S}(s_{S})$ such that $P'(s_{S})=w$. By minimality of $S$ the shape $w$ meets $\Vcal(s)$ for every $s \in V(S)$. Thus Corollary <ref> provides us with an arrangement $A$ on $S$ such that $A/S=A'$ and this arrangement satisfies $\varphi(A)=w$. The moreover part follows from Lemma <ref> <ref>.

We have just seen that every arrangement $A$ on an open subtree $S$ of $T$ represents a self-avoiding walk $\varphi(A)$ on $\Gcal(S)$ and that every such walk is represented by some arrangement. However, in general there can be several different arrangements representing a single walk. To enumerate SAWs on $G$, we need each walk to be represented by exactly one arrangement. This can be done by restricting ourselves to complete arrangements, as the upcoming Theorem <ref> shows. For its proof, we need the following auxiliary result.

Let $A=(P,C)$ be a complete arrangement on an open subtree $S$ of $T$ and let $t$ be a leaf of $S$. Then $P(t)$ contains a non-virtual arc.

Let $t$ be a leaf of $S$. If $S=\sta(t)$, completeness implies that $X(e)=\bar e$ for every $e \in E(S)$. Thus by <ref> the shape $P(t)$ starts with a non-virtual arc.

Suppose now that $S$ is not an open star and let $f$ be the unique arc in $\Eout(t)\setminus \partial E(S)$. By completeness of $A$ we have $X(e)=Y(e)=\bar e$ for every $e \in \partial E(S)$. If $X(f)=\bar f$ or $Y(f)=\bar f$, then again  $P(t)$ has to start or end with a non-virtual arc. Thus we may assume that $X(f)=Y(f)=f$. By reducedness $C(f)$ is not boring, so $Q(f)$ has to contain a virtual arc in $\Ecal(\bar f)$. Then by compatibility <ref> the shape $P(t)$ contains a sub-walk $p$ connecting the two endpoints of this walk. Now $C(e)$ is boring for every $e \in \partial E(S)$ and thus $p$ cannot contain any virtual arcs. We conclude that $P(t)$ contains a non-virtual arc.

Let $w$ be a self-avoiding walk on $G$. Then there is a unique complete arrangement representing $w$.

We start by constructing a representation of $w$ as in the proof of Theorem <ref>. Let $S$ be the support of $w$ in $T$ and let $S'=\sta_{T/S}(s_{S})$. Then Lemma <ref> <ref> provides us with an arrangement $A'=(P',C')$ on $S'$ such that $P'(s_{S})=w$. Note that we can choose $A'$ to be complete: The walk $w$ starts and ends with a non-virtual arc and $X'(e)=Y'(e)=\bar e$ is a valid choice for every $e \in E(S')$. Additionally, all arcs of $w$ are non-virtual arcs of $\Gcal(S)=\Gcal(s_S)$, thus $Q'(e)$ contains only arcs in $\Ecal(\bar e)$ and $C'(e)$ is boring. Corollary <ref> provides us with an arrangement $A$ on $S$ such that $A/S=A'$ and thus $\varphi(A)=w$. By Lemma <ref> whenever $C(e)$ is boring for some arc $e$ of $S$, $P(s)$ cannot contain any non-virtual arcs for every $s \in V(K_{X(e)}) \cap V(S)$. By minimality of $S$ we conclude $e \in \partial E(S)$. Thus $A$ is complete.

For the uniqueness part, observe that whenever $A$ is a complete arrangement on a subtree $S$ of $T$ representing $w$, by Lemma <ref> this subtree must be the support of $w$. By Corollary <ref> each $A$ corresponds to a unique arrangement $A/S$ on $S'$ and clearly $A/S$ must be complete. By completeness $X/S(e)=Y/S(e)=\bar e$ holds for every $e \in E(S')$ and by Lemma <ref> <ref> the configuration $C/S(e)$ is uniquely defined by $w=P/S(s_S)$, so $A/S$ is uniquely defined by $w$.

For any complete arrangement $A$ on a finite open subtree $S$ of $T$ there is exactly one vertex $s_0$ of $S$ such that $X(e)=\bar e$ for every $e \in \Eout(s_0)$. This can be easily seen by double counting the set $\{(s,e) \mid e^-=s \text{ and } X(e) = e\}$ and using <ref> and that configurations on boundary arcs $e$ satisfy $X(e)=\bar e$. We call $s_0$ the source of the complete arrangement $A$.
Similarly there is a unique vertex $t_0$ of $S$ such that $Y(e)=\bar e$ for every $e \in \Eout(t_0)$ and this vertex is called the target of $A$.

Let $A$ be a complete arrangement representing a SAW $w$ on $G$. The part graph $\Gcal(s_0)$ of the source $s_0$ of $A$ contains the first arc of $w$. Similarly, the graph $\Gcal(t_0)$ of the target $t_0$ contains the final arc of $w$.

Observe that for any $t \in V(T)$ by Construction <ref> the walk $P(t)$ visits exactly the vertices in $w \cap \Vcal(t)$ in the same order as $w$. Let $t$ be a vertex of $T$ such that $w^- \in \Vcal(t)$ and let $s$ be the neighbour of $t$ on the unique $s_0$–$t$-path and let $e=st$. Then $X(e)=e$, so by <ref> the initial vertex $w^-$ of $P(t)$ must be in $\Ecal(e)$ and thus $w^- \in \Vcal(s)$. Induction yields $w^- \in \Vcal(s_0)$.
By <ref> the first arc of $P(s_0)$ is non-virtual and thus coincides with the first arc of $w$.
The statement about the target follows analogously.

§ A GENERATING SYSTEM OF EQUATIONS FOR CONFIGURATIONS

Throughout this section let $G$ be a locally finite connected graph and let $\Gamma$ be a group acting quasi-transitively on $G$. We always assume that $\Gamma$ does not fix an end of $G$. Corollary <ref> provides us with a $\Gamma$-invariant tree decomposition $(\Tcal,\Vcal)$ of $G$ such that there are exactly two $\Gamma$-orbits on the arcs of $T$. More precisely, we can pick an arc $e_0$ such that every arc $e$ of $T$ either lies in the orbit $\Gamma e_0$ or in the orbit $\Gamma \bar e_0$. We denote by $\rho(e) \in \{e_0, \bar e_0\}$ the respective representative of the arc $e$.

Two non-boring configurations $c=(q,x,y)$ and $c'=(q',x',y')$ on the arcs $e$ and $e'$ of $T$ are $\Gamma$-equivalent if $(q',x',y')=(\gamma(q), \gamma(x), \gamma(y))$ holds for some $\gamma \in \Gamma$, where $\gamma(q)$ refers to the natural extension of $\gamma$ to the virtual edges. Clearly this defines an equivalence relation on the set of configurations on $E(T)$. Let $\Ccal$ be a set of representatives chosen in a way such that each $c \in \Ccal$ is a non-boring configuration on the arc $e_0$. Observe that the set $\Ccal$ has finite cardinality because the adhesion graph $\Gcal(e_0)$ is finite and thus carries only finitely many different configurations. For any non-boring configuration $c$ we denote its representative in $\Ccal$ by $\rho(c)$.

Let $c=(q,x,y)$ be a non-boring configuration. A $c$-completion is an arrangement $A=(P,C)$ on a finite open sub-tree $S$ of $K_{x}$ containing $x$ such that $C(x)=c$ and $C(e)$ is boring on $e \in E(S)$ if and only if $e \in \partial E(S) \setminus \{x\}$. We define the generating function of $c$-completions as

\[
F_{c}(z)=\sum_{\text{$A$ $c$-completion}} z^{\norm{A}},
\]

Let $r_c$ denote the radius of convergence of the generating function $F_c(z)$ and let $R=\min_{c \in \Ccal} r_c$.

The main goal in this section is to find a system of equations for the generating functions of $c$-completions and study this system to obtain properties of these generating functions.

For an arrangement $A$ on an open subtree $S$ of $T$ and a vertex $s$ of $S$, we denote by $\nb(A,s)$ the set of arcs $e \in \Eout(s)$ such that $A$ is non-boring on $e$. Observe that by definition $\nb(A,s)$ is a finite set.

Let $c=(q,x,y)$ be a configuration and let $A=(P,C)$ be a $c$-completion on the open cone $K_x$. Then we can decompose $A$ into its restriction $A_S$ on the open star $S=\sta(x^-)$ and $C(e)$-completions $A_e$ on the cones $K_{\bar{e}}$ for all outgoing arcs $e$ of $S$ different from $x$. Observe that Lemma <ref> implies that whenever $C(e)$ is boring, the arrangement $A_e$ is uniquely given by $C(e)$ and does not contain any non-virtual arcs. Thus it is possible to recursively build all $c$-completions by completing arrangements $A$ on $\sta(x^-)$ satisfying $C(x)=c$ with $C(e)$-completions for all $e \in \Eout(x^-)\setminus \{x\}$ carrying non-boring configurations $C(e)$. Thus we obtain

\begin{equation}\label{eq:defPc}
F_{c}(z) = \sum_{\substack{A \text{ arr. on } \sta(x^-): \\ C(x)=c}} z^{\norm{A}} \prod_{e \in \nb(A,x^-) \setminus \{x\}} F_{C(e)}(z).
\end{equation}

It follows from the definitions that $F_c(z)=F_{c'}(z)$ whenever $c$ and $c'$ are $\Gamma$-equivalent configurations. Write $\Fbf(z)=(F_{c}(z))_{c \in \Ccal}$. Then the equations above can be rewritten by replacing every $F_c(z)$ by $F_{\rho(c)}(z)$ to obtain

\begin{equation}
F_{c}(z)=P_{c}(z,\Fbf(z)), \quad c \in \Ccal. \label{eq:soe}
\end{equation}

\begin{equation*}
P_c(z,\mathbf y)= \sum_{\mathbf{n} \in \N_0^{\abs{\Ccal}}} a_{c,\mathbf{n}}(z) \mathbf{y}^\mathbf{n}, \quad c \in \Ccal,
\end{equation*}

is a formal power series in the variables $\mathbf y=(y_c)_{c \in \Ccal}$ whose coefficients are formal power series $a_{c,\mathbf n}(z)$ in the variable $z$ given by the sums in equation (<ref>), respectively, where

\[
\mathbf{y}^\mathbf{n}=\prod_{c \in \Ccal} y_c^{n_c}
\]

for an exponent vector $\mathbf{n}=(n_c)_{c \in \Ccal}$.

Let $c \in \Ccal$ be a non-boring configuration. By Lemma <ref> each $c$-completion contains at least one non-virtual arc, so that $F_c(0)=0$. Furthermore we may assume without loss of generality that $F_c(z)$ is not identically zero, that is, that there exists at least one $c$-completion. If this is not the case for some configuration $c \in \Ccal$, we remove $c$ from $\Ccal$ and replace every occurrence of $y_c$ in $P_c(z,\ybf)$ by $0$. Observe that after this process equations (<ref>) remain valid.

Consider the Jacobian matrix

\[
\Jac(z,\ybf)=\left(\frac{ \partial P_{c}}{\partial y_{c'}}(z,\ybf)\right)_{c,c' \in \Ccal}.
\]

Let $c=(q,x,y)$ and $c'$ be two non-boring configurations. A $c$–$c'$-completion is an arrangement $A=(P,C)$ on a finite open subtree $S$ of $K_x$ containing $x$ such that $C(x)=c$ and there is an arc $f \in \partial E(S)$ such that $\rho(C(f))=c'$ and $C(e)$ is boring on $e \in E(S)$ if and only if $e \in \partial E(S) \setminus \{x,f\}$. The arc $x$ is the source arc of the $c$–$c'$-completion $A$ and $f$ is the target arc. The length of $A$ is the  between the source arc $x$ and the target arc $f$. We denote by $\Acal(c,c',n)$ the set of $c$–$c'$-completions of length $n$.

Let us now take a closer look at the entries of $\Jac(z,\Fbf(z))$. To simplify notation, for any expression $\phi(z,\ybf)$ depending on the variable $z$ and the vector $\ybf$, we denote its evaluation at $\ybf=\Fbf(z)$ by

\[
\phi(z)=\phi(z,\Fbf(z)).
\]

Let $c,c'$ be non-boring configurations. Then

\[
(\Jac(z))_{c,c'}= \sum_{ A \in \Acal(c,c',1)} z^{\norm{A}}.
\]

Let $c=(q,x,y)$. From equations (<ref>) and (<ref>) we obtain

\[
P_c(z,\ybf)= \sum_{\substack{A \text{ arr. on } \sta(x^-): \\ C(x)=c}} z^{\norm{A}} \prod_{e \in \nb(A,x^-) \setminus \{x\}} y_{\rho(C(e))}.
\]

An application of the Leibniz rule provides

\[
\frac{ \partial P_{c}}{\partial y_{c'}}(z,\ybf) =\sum_{\substack{A \text{ arr. on } \sta(x^-): \\ C(x)=c}} z^{\norm{A}} \sum_{\substack{f \in \nb(A,x^-) \setminus \{x\}: \\ \rho(C(f))=c'}} \quad \prod_{e \in \nb(A,x^-) \setminus \{x,f\}} y_{\rho(C(e))}
\]

By definition every $c$–$c'$-completion $A$ of length $1$ consists of an arrangement $A_s=(P_s,C_s)$ on $\sta(x^-)$ such that there is an arc $f \in \Eout(x^-) \setminus \{x\}$ with $\rho(C_s(f))=c'$ and $C_s(e)$-completions $A_e$ for all $e \in \nb(A,x^-) \setminus \{x,f\}$. Conversely, every such $A_s$ together with some $C_s(e)$-completions $A_e$ forms a $c$–$c'$-completion. Finally note that in this case

\[
\norm{A}=\norm{A_s} + \sum_{e \in \nb(A,x^-) \setminus \{x,f\}} \norm{A_e}.
\]

We conclude

\[
(\Jac(z))_{c,c'}= \sum_{ A \in \Acal(c,c',1)} z^{\norm{A_s}} \prod_{e \in \nb(A_s,x^-) \setminus \{x,f\}} F_{\rho(C_s(e))} = \sum_{ A \in \Acal(c,c',1)} z^{\norm{A}}.
\]

Observe that a $c$–$c''$-completion $A_1$ and a $c''$–$c'$-completion $A_2$ can be concatenated to obtain a $c$–$c'$-completion whose length is the sum of the lengths of $A_1$ and $A_2$. In particular, the matrix counting $c$–$c'$-completions of length $n$ can be obtained as the $n$-th power of the matrix of $c$–$c'$-completions of length $1$.

Let $c,c'$ be non-boring configurations and denote $\Acal(c,c',n)$ the set of $c$–$c'$-completions of length $n$. Then

\[
(\Jac(z)^n)_{c,c'}= \sum_{ A \in \Acal(c,c',n)} z^{\norm{A}}.
\]

The dependency digraph $D$ of the system of equations (<ref>) is given as follows. Its vertex set is the set $\Ccal$ of representatives of configurations and there is an arc from $c=(q,x,y)$ to $c'$ if $\frac{\partial P_{c}}{\partial y_{c'}}(z)$ is non-zero. In this case we also write $c \rightarrow c'$. Recall that we removed all $c$ such that $F_c(z)$ is identically zero from $\Ccal$. Therefore we have that $c \rightarrow c'$ if and only if $y_{c'}$ occurs in the power series $P_{c}$, that is, if $a_{c',\mathbf{n}}(z) > 0$ for some $\mathbf{n}=(n_c)_{c \in \Ccal}$ with $n_{c'}>0$. By definition this is the case if and only if there is a $c$-completion $A=(P,C)$ such that $\rho(C(f))=c'$ holds for some $f \in \Eout(x^-) \setminus \{x\}$.

The following lemma follows readily from the definitions.

If $c \rightarrow c'$ for two configuration $c,c' \in \Ccal$, then $r_{c} \leq r_{c'}$.

We further classify configurations as follows. A configuration $c=(q,x,y)$ is called an I-configuration if $x \neq y$ and it is called a U-configuration if $x=y$. We denote the respective subsets of $\Ccal$ by $\Ical$ and $\Ucal$, so that $\Ccal=\Ical \cup \Ucal$ is a disjoint union. We call $c \in \Ical$ simple, if $q$ consists only of a single vertex and denote by $\Ical_s$ the set of simple configurations. Furthermore, we call $c \in \Ical$ persistent, if there are two simple configurations $c_1$ and $c_2$ such that $c$ lies on a walk from $c_1$ to $c_2$ in $D$. Note that this is equivalent to the existence of a $c_1$–$c_2$-completion such that there is some arc $e$ of the shortest walk from the source arc to the target arc for which $C(e)$ is equivalent to $c$. Non-persistent I-configurations are called transient and we denote by $\Ical_p$ and $\Ical_t$ the sets of persistent and transient configurations, respectively. Note in particular that all simple configurations are persistent.

Let $e, f \in E(T)$. Then there is an arc $f' \in \Gamma f$ such that for every pair of simple configurations $c=(q,x,y) , c'=(q',x',y')$ with entry directions $x=e$ and $x'=\bar f$ there is a $c$–$c'$-completion with target arc $f'$.

Let $N$ be the constant defined in Proposition <ref>. Proposition <ref> provides an automorphism $\gamma \in \Gamma$ such that $e$ and $f'=\gamma(f)$ are linkable and have  at least $N$. Let $u$ be the single vertex of $q$ and $v$ be the single vertex of $\gamma(q')$. Then Proposition <ref> provides us with a SAW $w$ connecting $u$ and $v$ and meeting $\Vcal(e)$ and $\Vcal(f')$ only in these vertices.

Theorem <ref> provides us with a representation $A=(P,C)$ of the SAW $w$ on its support $S$ such that $X(e)=e$ and $Y(f')=f'$. It is easy to check that this representation is a $c$–$c'$-completion with target arc $f'$.

The previous lemma immediately implies that $r_c \leq 1$ holds for the radius of convergence $r_c$ of $F_c$ for every simple configuration $c \in \Ical_s$. Indeed, the walk represented by a $c$-$c'$-completion is also represented by a $c$-completion, thus $F_c(z)$ contains infinitely many non-zero coefficients.

The dependency-digraph $D$ satisfies the following conditions.

* There are no arcs from U-configurations to I-configurations.

* Each strong component is contained in one of the sets $\Ical_p$, $\Ical_t$ and $\Ucal$. We call components persistent, transient or U-components depending on the type of configurations they contain.

* The set $\Ical_p$ is a strong component of $D$.

Let $c=(q,x,y) \in \Ccal$ be a U-configuration and let $A=(P,C)$ be an arrangement on $\sta(x^-)$ such that $C(x)=c$. As $c$ is a U-configuration, $x=y \in \Eout(x^-)$, so by <ref> and <ref> in the definition of arrangements $X(f)=Y(f) = \bar f$ holds for every $f \in \Eout(x^-) \setminus \{x\}$, thus $C(f)$ is a U-configuration. In particular $D$ cannot contain arcs from U-configurations to I-configurations.

Lemma <ref> shows that all simple configurations are contained in the same strong component of $D$. Furthermore, persistent configurations are defined to lie on paths between simple configurations, so all of them are contained in this component, showing that $\Ical_p$ is contained in a single strong component.

Now let $\Kcal$ be an arbitrary strong component in $D$. If $\Kcal$ contains a U-configuration, then <ref> implies that $\Kcal$ cannot contain any I-configuration, so $\Kcal \subseteq \Ucal$.

Next assume that $\Kcal$ contains a transient configuration. Recall that by definition a transient configuration $c$ cannot lie on a $c_1$–$c_2$-path in $D$ for two simple configurations $c_1,c_2$. Hence, if $\Kcal$ contains a transient configuration, it cannot contain a simple configuration, so in this case $\Kcal \subseteq \Ical_t$.

Finally, if $\Kcal$ contains neither U-configurations nor transient configurations, then it is contained in $\Ical_p$. Since all of $\Ical_p$ is contained in a single strong component we conclude that in this case $\Kcal = \Ical_p$, in particular $\Ical_p$ is a strong component.

The submatrix obtained from $\Jac(z)$ by restricting the index set to some subset $\Kcal \subset \Ccal$ is denoted by $\Jac_\Kcal(z)$.
It follows directly from Lemma <ref> that if $\Kcal$ is a strong component of $D$, the radii of convergence $r_c$ coincide for all $c \in \Kcal$. We denote the common value by $r_\Kcal$. Let $c \in \Kcal$ and let $c' \in \Ccal$ such that $c \rightarrow c'$. Then Lemma <ref> implies that $F_{c'}(z)$ is well-defined and finite for $0\leq z < r_\Kcal$. Hence $\Jac_\Kcal(z)$ is well defined for $0\leq z < r_\Kcal$.
Denote the spectral radius of the matrix $\Jac_\Kcal(z)$ by $\lambda_\Kcal(z)$.

Let us now state some properties of $\Jac_\Kcal(z)$ and $\lambda_\Kcal(z)$ which will be important later on.

For each strong component $\Kcal$ of $D$ the following statements hold.

* All entries of $\Jac_\Kcal(z)$ are continuous, non-negative, and non-decreasing in $[0, r_\Kcal)$.

* The spectral radius $\lambda_\Kcal(z)$ is continuous and non-decreasing in $[0, r_\Kcal)$. Additionally, $\lambda_{\Ical_p}(z)$ is strictly increasing in $[0, r_{\Ical_p})$

* $\Jac_\Kcal(0)$ is nilpotent, in particular $\lambda_\Kcal(0)=0$.

By Lemma <ref>, the entries of the matrix $\Jac_{\Kcal}(z)$ are generating functions counting $c$–$c'$-completions of length 1 for $c,c' \in \Kcal$. In particular they are continuous, non-negative and non-decreasing within their radius of convergence and the same holds for the spectral radius $\lambda_\Kcal(z)$.

By Proposition <ref>, there are two persistent configurations $c, c'$ such that  $(\Jac_{\Ical_p}(z))_{c,c'}$ is non-constant and thus strictly increasing in $z$. Irreducibility of $\Jac_{\Ical_p}(z)$ implies that also $\lambda_{\Ical_p}(z)$ is strictly increasing in $z$.

To see that (iii) holds, note that by Corollary <ref> for $n$ large enough, any arcs $e,f \in E(T)$ of  at least $n$ satisfy $\Vcal(e) \cap \Vcal(f) = \emptyset$. By Corollary <ref> the entries of $\Jac_{\Kcal}(z)^n$ are generating functions counting $c$–$c'$-completions $A$ of length $n$. But the walk represented by such an arrangement $A$ connects $\Vcal(e)$ and $\Vcal(f)$ and thus must be non-trivial. In particular the respective entry of $\Jac_{\Kcal}(z)^n$ has no constant term, so $\Jac_{\Kcal}(0)^n=0$.

Our aim now is to show that $\Jac_\Kcal(z)$ has finite entries at $z=r_{\mathcal{K}}$ for every strong component $\Kcal$.

For each strong component $\Kcal$ of $D$, the matrix $\Jac_\Kcal(r_{\mathcal{K}})$ is well-defined and has finite entries. Moreover, $\lambda_{\mathcal{K}}(z)< 1$ for every $0\leq z<r_{\mathcal{K}}$ and $\lambda_{\mathcal{K}}(r_{\mathcal{K}})\leq 1$.

In order to prove this lemma, we first need the following result.

Let $A=(a_{ij})\in \mathbb{R}^{n\times n}$ be an irreducible matrix such that $a_{ij}\geq 0$ for every $i,j\in\{1,2,\ldots,n\}$ and $\lambda(A)\leq 1$. Let also $M=\max\{a_{ij} \}$ and $m=\min\{a_{ij} \mid a_{ij}>0\}$. Then $M\leq m^{-n}$.

Consider some $i_0,j_0$ such that $a_{i_0j_0}=M$. By the irreducibility of $A$, there are $l\leq n$ and indices $z_1=j_0,z_2,\ldots,z_l=i_0$ with $a_{z_iz_{i+1}}>0$ for every $i=1,2,\ldots,l-1$. The entry $a^{(l)}_{i_0i_0}$ of the matrix $A^l$ satisfies

\[a^{(l)}_{i_0i_0}\geq a_{i_0j_0}\prod_{i=1}^{l-1} a_{z_i z_{i+1}}\geq Mm^{l-1}.\]

Since $A^l$ has non-negative entries and $\lambda(A^l)=\lambda(A)^l\leq 1$, we have by the monotonicity of the spectral radius that

\[1 \geq \lambda(A^l)\geq \lambda(B)=Mm^{l-1},\]

where $B$ is the matrix with $b_{i_0i_0}=Mm^{l-1}$, and all other entries 0.
In particular we see that $m \leq 1$, so $M \leq m^{-l+1} \leq m^{-n}$.

For each strong component $\mathcal{K}$ of $D$, let $F_{\mathcal{K}}(z)=(F_c(z))_{c\in\mathcal{K}}$. Additionally for $\ybf=(y_c)_{c \in \Kcal}$ let $P_{c',\Kcal}(z,\ybf)$ be obtained from $P_{c'}(z,(y_c)_{c \in \Ccal})$ by substituting $y_c=F_c(z)$ for each $c \in \Ccal \setminus \Kcal$.

We are now ready to prove Lemma <ref>.

Let us start by showing that

\begin{equation}\label{leq1}
\lambda_{\mathcal{K}}(z)< 1 \text{ for every } 0\leq z< r_{\mathcal{K}}.
\end{equation}

We will argue as in <cit.>.

Assume for a contradiction that $\lambda_{\mathcal{K}}(z_0)\geq 1$ for some $0\leq z_0< r_{\mathcal{K}}$. Since $\lambda_{\mathcal{K}}(0)=0$ and $\lambda_{\mathcal{K}}(z)$ is continuous, there is some $0<s\leq z_0<r_{\mathcal{K}}$ such that $\lambda_{\mathcal{K}}(s)=1$. By the Perron-Frobenius Theorem for non-negative irreducible matrices,  $\lambda_{\mathcal{K}}(s)=1$ is a positive simple eigenvalue of $\Jac_{\mathcal{K}}(s)$ for which we can find a a left eigenvector $\mathbf{x}=(x_c)_{c\in \mathcal{K}}$ with only positive entries.
Define the function

$$\mathcal{F}(z,\mathbf{y})=\sum_{c\in \mathcal{K}}x_c\left(y_c-P_{c,\Kcal}(z,\mathbf{y})\right),$$

where $\mathbf{y}=(y_c)_{c\in\mathcal{K}}$.
Note that for $\zeta=\left(s,F_{\mathcal{K}}(s)\right)$ there is some $\beta \geq 0$ such that

\begin{equation*}
\begin{gathered}
\mathcal{F}(\zeta)=0,
\quad
\frac{\partial\mathcal{F}}{\partial z}(\zeta)=-\beta,
\quad
\frac{\partial\mathcal{F}}{\partial y_{c}}(\zeta)=0.
\end{gathered}
\end{equation*}

We claim that $\beta$ is strictly positive, that is, that there is some $c \in \Kcal$ such that $P_{c,\Kcal}(z,\mathbf{y})$ depends non-trivially on $z$. Recall that by Lemma <ref> every $c'$-completion contains a non-virtual arc, and thus $F_{c'}(z)$ depends on $z$ for every $c'$. If the strong component $\Kcal$ of $D$ has an outgoing arc $c c'$, then $P_{c,\Kcal}$ includes $F_{c'}(z)$, which depends on $z$. Otherwise for $c \in \Kcal$, the function  $P_{c,\Kcal}(z,\mathbf{y})=P_{c}(z,\mathbf{y})$ does not depend on any $y_{c'}$ for $c' \in \Ccal \setminus \Kcal$ and thus must depend on $z$, because $F_c(z)=P_{c}(z,\mathbf{F}(z))$ does.

Taylor expanding around $\zeta$, replacing $\ybf$ by $F_{\mathcal{K}}(z)$, and using that $F_c(z)=P_{c,\Kcal}(z,F_{\mathcal{K}}(z))$ we obtain

\begin{equation*}
\begin{gathered}
\beta(s-z)=O\left((s-z)^2\right),
\end{gathered}
\end{equation*}

which is a contradiction. This proves (<ref>).

We will now show that $\Jac_{\Kcal}(r_{\Kcal})$ has finite entries. Let us write $m(z)$ for the smallest positive entry of $\Jac_{\Kcal}(z)$, and consider some $0<z_1<r_{\mathcal{K}}$.
Then $\Jac_{c,c'}(z) \leq m(z)^{-|\mathcal{K}|}\leq m(z_1)^{-|\mathcal{K}|}$ for every $c,c'\in \mathcal{K}$ and every $z_1\leq z<r_{\mathcal{K}}$ by Lemma <ref> and the monotonicity of $m(z)$. It follows from the monotone convergence theorem that $\Jac_{c,c'}(r_{\mathcal{K}})$ is well-defined and $\Jac_{c,c'}(r_{\mathcal{K}})\leq m(z_1)^{-|\mathcal{K}|}$ for every $c,c'\in \mathcal{K}$, which proves the first assertion of the lemma.

For the second assertion, it remains to show that $\lambda_{\mathcal{K}}(r_{\mathcal{K}})\leq 1$. This follows from (<ref>) by taking the limit as $z$ goes to $r_{\mathcal{K}}$.

§ ANALYTICITY AT THE CRITICAL POINT

Keeping all definitions and assumptions from the previous section, the goal in this section is to prove the following analyticity results; recall that $R = \min_{c \in \Ccal} r_c$ is the minimal radius of convergence of any $F_c(z)$.

For every $c\in \Ucal$, $P_c(z,\ybf)$ is analytic at $(z,\ybf)=(R,\Fbf(R))$.

We have that $\Jac_{\Ical}(z,\ybf)$ is analytic at $(z,\ybf)=(R,\Fbf(R))$.

We will prove Propositions <ref> and <ref> in a series of lemmas. We start by showing that $F_c(R)$ is finite for every $c\in \Ucal$.

If $T$ has more than two ends and $\Gamma$ does not fix an end of $T$, then $F_c(R)$ is well-defined and finite for every $c\in \Ucal$.

First note that every $c \in \Ucal$ is by definition non-boring and thus contains a virtual arc in $\Ecal(\bar x)$. If $c$ contains $k \geq 2$ virtual arcs $e_1, \dots e_k \in \Ecal(\bar x)$, then $F_c(z) \leq \prod_{i=1}^k F_{c_i}(z)$, where $c_i=(q_i,x,y)$ is the configuration such that $q_i$ is the walk of length 1 with the single arc $e_i$.
It thus suffices to prove the assertion for every $c=(q,x,y)\in \Ucal$ that contains exactly two vertices and a virtual arc in $\Ecal(\bar x)$ connecting those vertices. Let $c$ be such a configuration.

We claim that there are an open subtree $S$ of $T$, an arrangement $A=(P,C)$ on $S$ and three arcs $f,e_1,e_2 \in \partial E(S)$ satisfying the following conditions:

* $C(f)= c$ and $X(f)=\bar f$.

* $C(e_1)$ and $C(e_2)$ are simple I-configurations such that $X(e_1)=e_1$ and $Y(e_2)=e_2$.

* $C(e')$ is boring if and only if $e' \in \partial E(S) \setminus \{f,e_1,e_2\}$.

If such an arrangement $A$ exists, then $A$ together with a $c$-completion $A'$ forms a $C(e_1)$–$C(e_2)$-completion, whose length $n$ is the  of $e_1$ and $e_2$. In particular

\[
(\Jac_p(R)^n)_{C(e_1),C(e_2)} \geq R^{\norm{A}} F_c(R),
\]

so Lemma <ref> implies that $F_c(R)$ is finite.

For the proof of the claim we start by picking $f=\bar x$. Furthermore let $e_1, e_2$ be two different arcs having the same  to $f$. We pick $e_1$ and $e_2$ such that the sets $\Vcal(f)$, $\Vcal(e_1)$ and $\Vcal(e_2)$ are pairwise disjoint.

Let $q=(u,e,v) \in \Vcal(f)$. As in the proof of Proposition <ref> we can find two disjoint $\Vcal(f)$–$\Vcal(e_2)$-paths $\pi_{u}$ and $\pi_{v}$ in $G$, starting at $u$ and $v$, respectively. Moreover, we find a $\Vcal(f)$–$\Vcal(e_1)$-path $\pi$ in $G$ starting at $u$. Let $u'$ be the endpoint of $\pi$ in $\Vcal(e_1)$. We construct a walk $w$ on $\Gcal(K_f)$ as follows. Start at $u'$ and follow $\pi$ until its first intersection with one of the paths $\pi_{u}$ and $\pi_{v}$. If we reached $\pi_u$, we follow it until $u$, add the arc $e$ to reach $v$ and follow $\pi_v$ from $v$ to $\Vcal(e_2)$. Otherwise we follow $\pi_v$ until $v$, add $\bar e$ to reach $u$ and follow $\pi_u$ to reach $\Vcal(e_2)$. In this case we reverse the obtained walk and exchange $e_1$ and $e_2$. It is now easy to check that in both cases we end up with a SAW $w$ on $\Gcal(K_f)$ connecting $\Vcal(e_1)$ and $\Vcal(e_2)$ and containing the arc $e$. Let $S$ be the support of $w$. By construction the arcs $e_1,e_2$ and $f$ are in $\partial E(S)$. Theorem <ref> provides us with a representation $A=(P,C)$ of $w$ such that $X(e_1)=e_1$ and $Y(e_2)=e_2$. It is easy to check that $A$ satisfies conditions <ref>–<ref>.

The following construction is essential in the upcoming proofs; it is sketched in Figure <ref>.

[use Hobby shortcut,vertex/.style=inner sep=1pt,circle,draw,fill,rotate=10]

++(-45:1) arc (-45:-135:1) ++(-135:-1)
++(-45:1) arc (-45:-135:1) ++(-135:-1);

++(45:1) arc (45:135:1) ++(135:-1)
++(45:1) arc (45:135:1) ++(135:-1);

– ++(10:2)
arc (-80:20:1)
– ++(110:2);

– ++(10:-2)
arc (-80:20:-1)
– ++(110:-2);

[ultra thick]
[gray, ultra thick]

[ultra thick]
–++($(0,-.4) + (0:1) + (60:1) + (90:-.9)$)
–++($(90:.9) + (-50:.9)$)
–++($(130:.9) -(-1,1)$);
[shift = ($(0:1)+(60:1)$), xshift=3cm,rotate=180]
[ultra thick]
[vertex] at (-1,1);
[inner sep = 1pt, anchor=north west] at (-1,1)$g_e(u)$;
[inner sep = 1pt, anchor=south east] at (130:.9)$g_e(u')$;
[vertex] at (130:.9) ;

[vertex] at (-1,1);
[inner sep = 1pt, anchor=south east] at (-1,1)$u$;
[vertex] at (130:.9) ;
[inner sep =3pt,anchor=west] at (130:.9)$u'$;
[vertex] at (130:.9) ;

Reflection-extension  with splitting point $u$. The last part of the original walk is drawn in gray, the modified walk is drawn in black. Note that the distance between $u'$ and $g_e(u')$ is bounded by an absolute constant, so the increase in length will become negligible when the length of the original walk is large.

Let $a \in \{e_0, \bar e_0\}$ be a representative arc of the action of $\Gamma$ on $E(T)$ and fix an odd integer $N$ which is larger than or equal to the constant of Proposition <ref>. Then Proposition <ref> provides us with an automorphism $\gamma_{a}$ such that $a$ and $\gamma_{a}(a)$ are linkable and have  $N$. By Proposition <ref> for any $v \in \Vcal(a)$ there is a $v$–$\gamma_{a} v$-path $\pi_{a,v}$ in $G$ meeting $\Vcal(a) \cup \Vcal( \gamma_{a} a)$ only in its endpoints.

Moreover, for every $e \in E(T)$ fix an automorphism $h_e$ mapping $e$ to its representative $\rho(e) \in \{e_0,\bar e_0\}$.

Let $e \in E(T)$ and $w$ be a self-avoiding walk on $\Gcal(K_e)$ not intersecting $\Vcal(e)$. A reflection-extension of $w$ through $e$ is constructed as follows. Let $u$ be a vertex of $w$ such that $d_G(u,\Vcal(e))=d_G(w,\Vcal(e))$. We apply $g_e:=h^{-1}_{e}\circ \gamma_{h_e(\bar e)}\circ h_{e}$ to the sub-walk of $w$ starting at $u$. Next we connect $u$ to $\Vcal(e)$ with a geodesic in $G$, which by definition intersects $\Vcal(e)$ only in a single vertex $u'$. Furthermore we connect $g_e(u)$ to $\Vcal(g_e(e))$ with the image of the latter geodesic under $g_e$. Finally, we connect $u'$ to $g(u')$ with $h_e^{-1}(\pi_{h_e(\bar e),h_e(u')})$. Note that by our choice of the vertex $u$, the object we thus obtain is a SAW; we denote by $\refl_e(w)$ the set of all possible reflection-extensions of $w$ through $e$. The vertex $u$ is called splitting point of the reflection-extension.

Let $e \in E(T)$ and let $w_1$ and $w_2$ be different self-avoiding walks on $\Gcal(K_e)$. Then $\refl_e(w_1) \cap \refl_e(w_2) = \emptyset$.

We show that the walk $w$ can be uniquely reconstructed from any $w' \in \refl_e(w)$ provided that $e$ is known. Note that by construction $w'$ consists of 5 parts: the sub-walk of $w$ up to the vertex $u$, followed by a geodesic $\pi_u$ from $u$ to $u' \in \Vcal(e)$, a walk from $u'$ to $g_e(u')$, the image of $\pi_u$ under $g_e$, and the image of the sub-walk of $w$ starting at $u$ under $g_e$. In particular, given $w'$ it is easy to identify $u$ as the first vertex of $w'$ such that $g_e(u)$ is also contained in $w'$. Then $w$ is obtained as the concatenation of the sub-walk of $w'$ up to $u$ and the image of the sub-walk of $w'$ starting at $g_e(u)$ under the map $g_e^{-1}$.

Our next goal is to show that there are exponentially fewer SAWs that stay withing a part than SAWs that use vertices in multiple parts.  Consider some part $\Vcal(t)$ and some vertex $o\in \Vcal(t)$. We define $c_n(o,t)$ to be the number of SAWs $w$ on $G$ of length $n$ starting at $o$ visiting only vertices in $\Vcal(t)$. Let $\mu_{o,t}=\limsup c_n(o,t)^{1/n}$.

If $\Gamma$ does not fix an end of $T$, then $\mu_{o,t}<1/R$ for every $t\in V(T)$ and $o\in \Vcal(t)$.

The statement is trivially satisfied if $\Vcal(t)$ is finite, so we henceforth assume that $\Vcal(t)$ is infinite.
Consider a SAW $w$ of length $n$ starting at $o$ and visiting only vertices in $\Vcal(t)$. We will construct several SAWs starting at $o$ that do not stay in $\Vcal(t)$ by applying Construction <ref> and then compare the corresponding generating functions.

We first need to define a suitable set of adhesion sets. Let $M>0$ be the constant of Proposition <ref>. Let also $\Bcal(w)$ be a set of arcs of $\Eout(t)$ such that $1 \leq d_G(\Vcal(e),w) \leq M$ for every $e \in \Bcal(w)$, $d_G(\Vcal(e),\Vcal(f))>2M$ for every distinct $e, f\in \Bcal(w)$, and $\Bcal(w)$ is maximal with respect to the latter property.

We now associate to each $e\in \Bcal(w)$ a vertex $u_e=u_e(w)$ of $w$ such that $d_G(u_e,\Vcal(e))=d_G(w,\Vcal(e))\leq M$, and we denote the set thus obtained by $U$. Note that the vertices $u_e$ are distinct because $d_G(\Vcal(e),\Vcal(f))>2M$ for every distinct $e, f\in \Bcal(w)$. Using the ordering of the vertices $u_e$ coming from the ordering of the vertices of $w$, we order the elements of $\Bcal(w)$.

We claim that $|\Bcal(w)|\geq m:=n/\Delta^{4M+2D}$, where $\Delta$ is the maximal vertex-degree in $G$ and $D$ is maximal distance (in $G$) between two vertices in the sam adhesion set. Indeed, let $v$ be a vertex of $w$, and $f \in \Eout(t)$ such that $d_G(v,\Vcal(f))\leq M$. Then

\[
d_G\left(\Vcal(f),\bigcup_{e \in \Bcal(w)} \Vcal(e)\right)\leq 2M
\]

by the maximality of $\Acal(w)$. Hence $d_G(v,U)\leq 4M+2D$. This implies that the balls of radius $4M+2D$ around the vertices in $U$ cover $w$. Since each ball of radius $4M+2D$ has size at most $\Delta^{4M+2D}$, the claim follows.

Let $\varepsilon\in(0,1)$ be a small constant to be defined later, and consider a set $H\subseteq \Bcal(w)$ of cardinality $k=\lfloor \varepsilon m \rfloor$. We write $e_i=e_i(H)$ for the $i$th element of $H$. We will successively apply Construction <ref> to $w$.
More precisely, let $w_1(H) \in \refl_{e_1}(w)$ be a reflection-extension of $w$ through $e_1$ with splitting point $u_{e_1}$ and let $g=g_{e_1}$ be the automorphism applied to the second part of $w$ in the reflection-extension process.

Consider the second element $e_2\in H$, and note that $g(u_{e_2})$ minimizes $d_G(v, \Vcal(g(e_2)))$ among the vertices $v$ of $w_1(H)$, since

\[
\]

Thus there is a reflection-extension $w_2(H) \in \refl_{g(e_2)}(w_1(H))$ of $w_1(H)$ through $g(e_2)$ with splitting point $g(u_{e_2})$. Continuing in this way, we obtain a sequence of SAWs
$w_1(H),\ldots,w_k(H)$. Note that $w_k(H)$ has length between $n$ and
$n+k\ell$ for some constant $\ell>0$ independent of $w$.

Varying $H$ over all possible subsets of $\Bcal(w)$ of cardinality $k$, we obtain a map $(w,H) \mapsto w_k(H)$. We claim that this map is injective. Indeed, note first that the set $H$ can be reconstructed uniquely from $w_k(H)$. The arc $e_1(H)$ is the unique arc in $\Eout(t)$ such that the configuration defined by $w_k(H)$ on $e_1(H)$ is an I-configuration. This also defines uniquely the map $g=g_{e_1}$ used in the reflection-extension process. Similarly $g(e_2(H))$ is the unique arc in $\Eout(g(t)) \setminus \{e_1(H)\}$ such that the configuration defined by $w_k(H)$ on $g(e_2(H))$ is an I-configuration. Proceeding in this way, we see that $H$ is uniquely given by $w_k(H)$. But then the claim is a consequence of Lemma <ref>.

We have thus constructed at least

\[
\binom{m}{k}c_n(o,t)
\]

distinct SAWs that start at $o$ and have length between $n$ and $n+k\ell$.
Since $R \leq 1$ by Remark <ref>, this implies that

\[
R^{n+k\ell}\binom{m}{k} c_n(o,t) \leq \sum_{(w,H)}R^{\norm{w_k(H)}},
\]

where the sum runs over all SAWs $w$ of length $n$ starting at $o$ and all subsets $H$ of $\Bcal(w)$ of cardinality $k$. We will now estimate this sum in terms of $\Jac_p(R)$.

Each walk $w_k(H)$ is a self-avoiding walk starting at $\Vcal(t)$, and ending at $\Vcal(t')$, where $t'=(g_k \circ \dots \circ g_1)(t)$. Additionally, by construction $w_k(H)$ meets each of $e_1(H)$ and $e_k'(H):=(g_k \circ \dots \circ g_1)(e_k(H))$ only in a single vertex. Decomposing $w_k(H)$ at these two vertices, we see that it consists of a SAW $w_k^1(H)$ containing only vertices of $\Vcal(t)$, a SAW $w_k^2(H)$ connecting $\Vcal(e_1(H))$ and $\Vcal(e_k'(H))$ and a SAW $w_k^3(H)$ containing only vertices of $\Vcal(t')$. By Theorem <ref> there is a representation $A_H=(P_H,C_H)$ of $w_k^2(H)$ which is a $C_H(e_1(H))$–$C_H(e_k'(H))$-completion for the simple configurations $C_H(e_1(H))$ and $C_H(e_k'(H))$. By Construction <ref> the arcs $e_1(H)$ and $e_k'(H)$ have  $kN+k-1$. Thus the arrangement $A_H$ is counted in some entry of $\Jac_p(R)^{k N+ k-1}$.

Letting $c_n^t = \max_{o \in \Vcal(t)} c_n(o,t)$, we thus obtain

\[
\sum_{(w,H)}R^{\norm{w_k(H)}} \leq \norm{\Jac_p(R)}^{k N+ k-1}_1 \sum_{i=0}^n \sum_{j=0}^{n-i} c_i^t c_j^t R^{i+j}.
\]

To estimate the latter sum, let $\mu_{t}=\max_{v\in \Vcal(t)}\mu_{v,t}$.
By taking cases according to whether $\mu_t R \leq 1$ or $\mu_t R>1$ we obtain

\[
\sum_{i=0}^n \sum_{j=0}^{n-i} c_i^t c_j^t R^{i+j}=\max\{\mu_t^n R^n,1\}e^{o(n)}.
\]

This implies that

\[
c_n(o,t) \leq \frac{\max\{\mu_t^n,1/R^n\}}{R^{k\ell}\binom{m}{k}}\norm{\Jac_p(R)}^{k(N+1)+o(n)}_1.
\]

Recall that $k = \lfloor \varepsilon m \rfloor$. Hence by Stirling's approximation we obtain

\begin{equation}\label{eq:stirling}
\binom{m}{k}=\sqrt{\frac{m}{2\pi k(m-k)}}\frac{m^m}{k^k(m-k)^{m-k}}(1+o(1))=\left(\frac{1}{\varepsilon^\varepsilon(1-\varepsilon)^{1-\varepsilon}}\right)^{m+o(m)}.
\end{equation}

For $\varepsilon= R^{\ell}\norm{\Jac_p(R)}^{-(N+1)}_1$ we have

\[
c_n(o,t)\leq \max\{\mu_t^n, 1/R^n\}(1-\varepsilon)^{(1-\varepsilon)m+o(m)}.
\]

Taking $n$-th roots and sending $n$ to infinity we obtain that

Since this holds for all $o$, we obtain that $\mu_t<\max\{\mu_t,1/R\}$, hence $\mu_t<1/R$, as desired.

We are now ready to prove Proposition <ref>.

By assumption all coefficients of $P_c(z,\ybf)$ are non-negative. Thus it is enough to show that there is some constant $\delta > 0$ such that

\[
F_{c,\delta}(R) := P_c\left((1+\delta)R,(1+\delta)\Fbf(R)\right) < \infty.
\]

As in the proof of Lemma <ref>, it suffices to consider configurations $c\in \Ucal$ that contain only two vertices and a virtual arc connecting those vertices.

Let $c=(q,x,y)$ be such a configuration, and let $t=x^-$. Let us start by defining $\Acal(c,n)$ to be the set of arrangements $A=(P,C)$ on $S=\sta(t)$ such that $C(x)=c$ and $\abs{P(t)}=n$, where here $n$ counts the total number of arcs in $P(t)$ and not just the non-virtual ones. In particular every $A \in \Acal(c,n)$ satisfies

\begin{equation}\label{eq:nb-n}
\norm{A} + \abs{\nb(A,t) \setminus \{x\}} \leq n \leq \norm{A} + K \abs{\nb(A,t) \setminus \{x\}},
\end{equation}

where $K$ is the size of the adhesion sets of our tree decomposition.

With this in mind, we can write

\[
F_{c,\delta}(R) \leq  \sum_{n=0}^\infty (1+\delta)^n \Phi_{n}(R),
\]

\[
\Phi_{n}(R) = \sum_{A \in \Acal(c,n)} R^{\norm{A}} \prod_{e \in \nb(A,t) \setminus \{x\}} F_{C(e)}(R).
\]

It is enough find an upper bound for $\Phi_{n}(R)$ which decays exponentially in $n$ because then for some $\delta > 0$ small enough, $F_{c,\delta}(R)$ is upper bounded by a geometric series.
We split the inner sum into three parts and treat those parts individually. In order to split up the sum, we first need some definitions.

For $\varepsilon>0$ we partition $\Acal(c,n)$ into two subsets according to whether they result in a `small' or `large' number of non-boring configurations on the edges of $E(S)$:

* $\mathcal{S}(c,\varepsilon,n)$ is the set of  $A\in \Acal(c,n)$ such that the number of arcs $e\in E(S)\setminus\{x\}$ for which $C(e)$ is non-boring, is smaller than $\varepsilon n$,

* $\mathcal{L}(c,\varepsilon,n)=\Acal(c,n)\setminus \mathcal{S}(c,\varepsilon,n)$.

\begin{equation}
\label{eq:innersum}
\Phi_{n}(R) = \sum_{A \in \mathcal{S}(c,\varepsilon,n)} R^{\norm{A}} \prod_{e \in \nb(A,t) \setminus \{x\}} F_{C(e)}(R)
+ \sum_{A \in \mathcal{L}(c,\varepsilon,n)} R^{\norm{A}} \prod_{e \in \nb(A,t) \setminus \{x\}} F_{C(e)}(R).
\end{equation}

We further split the second sum into a part summing over completions where `many' of the $C(e)$-completions are longer than some constant $L$, and a part summing over completions where `few' of the $C(e)$-completions are longer than $L$.
More precisely, for $L>0$ and $A\in \mathcal{L}(c,\varepsilon,n)$, let $\mathcal{M}(A,\varepsilon,n,L)$ be the set of sequences $(A_e)_{e\in E(S)\setminus \{x\}}$, where each $A_e=(P_e,C_e)$ is an arrangement on $K_{\bar e}$, such that $C_e(e)=C(e)$ for every $e\in E(S)\setminus \{x\}$, and for at least $\varepsilon n/2$ arcs $e\in E(S)\setminus \{x\}$, we have $\norm{A_e}\geq L$. Let $\mathcal F(A, \varepsilon,n,L)$ be the set of sequences $(A_e)_{e\in E(S)\setminus \{x\}}$ not contained in $\mathcal M(A,\varepsilon,n,L)$.
Write $\norm{(A_e)}=\sum_{e\in E(S)\setminus \{x\}}\norm{A_e}$.

Recall that

\[
F_{C(e)}(R) = \sum_{A_e \; C(e)\text{-completion}} R^{\norm{A_e}}.
\]

Using this identity on the factors of the product inside the second sum in the expression (<ref>), we arrive at
\Phi_{n}(R) = \Sigma_{n}(R) + \Lambda_{n}^1(R)+ \Lambda_{n}^2(R),

\begin{align*}
\Sigma_{n}(R) & =  \sum_{A \in \mathcal{S}(c,\varepsilon,n)} R^{\norm{A}} \prod_{e \in \nb(A,t) \setminus \{x\}} F_{C(e)}(R) \\
\Lambda_{n}^1(R) & =  \sum_{A\in \mathcal{L}(c,\varepsilon,n)} R^{\norm{A}} \sum_{(A_e)\in \mathcal{M}(A,\varepsilon,n,L)} R^{\norm{(A_e)}}  \\
\Lambda_{n}^2(R) & =  \sum_{A\in \mathcal{L}(c,\varepsilon,n)} R^{\norm{A}} \sum_{(A_{e})\in \mathcal{F}(A,\varepsilon,n,L)} R^{\norm{(A_{e})}}.
\end{align*}

Let us first consider $\Sigma_n(R)$. Using the upper bound in (<ref>) together with the fact that $R \leq 1$ by Remark <ref>, we immediately obtain

\[
\Sigma_n(R) \leq  t_1^{\varepsilon n} R^{(1-K \varepsilon) n} \abs{ \mathcal{S}(c,\varepsilon,n)} ,
\]

where $1<t_1:=1+\max\{F_c(R)\mid c\in \Ucal\}$ is a finite constant by Lemma <ref>.
We will show that the right-hand side of the inequality decays exponentially, provided that $\varepsilon$ is small enough.

Let us estimate the cardinality of $\mathcal{S}(c,\varepsilon,n)$. Each $A=(P,C) \in \mathcal{S}(c,\varepsilon,n)$ consists of a walk $P(t)$ and a collection of configurations $(C(e))_{e \in E(S)}$ with all but at most $\varepsilon n$ of them being boring.
Note that $P(t)$ already uniquely determines $A$ because $c$ is a U-configuration. Indeed, the configurations $C(e)=(Q(e),X(e),Y(e))$ must be U-configurations and by Lemma <ref> each $Q(e)$ is determined by $P(t)$.
We derive an upper bound for the number of possible walks $P(t)$. We start by counting the possible walks with exactly $k$ virtual arcs, and whose walk components after removing the virtual arcs have lengths $(n_0,\dots, n_k)$. It is possible that some $n_i=0$. Note that $\sum_{i=0}^k n_i = n-k$. Denote the set of such walks by $\Wcal(n_0,\dots, n_k)$. We can construct such walks inductively. Start by choosing a walk $W_0$ of length $n_0$ starting at the initial vertex of the walk $q$ of the configuration $c$. In the $i$-th step we attach a virtual arc $e_i$ and a walk $W_i$ of length $n_i$ to the walk constructed so far; if no suitable virtual arcs exists, we do not proceed with the construction.
There are at most $c_{n_i}(t)$ ways to choose the $i$-th walk, and there is a constant upper bound $t_2$ for the number of virtual arcs incident to a vertex. Thus

\[|\Wcal (n_0,\dots n_k)| \leq t_2^{k}\prod_{i=0}^k c_{n_i}(t),\]

where $c_{n_i}(t)=1$ if $n_i=0$.
To bound this product, consider some $r\in (\mu_t,1/R)$, where $\mu_t=\max_{o\in \Vcal(t)} \mu_{o,t}$ Note that such an $r$ exists by Lemma <ref> and that there exists a constant $t_3\geq 1$ such that $c_m(t)\leq t_3 r^m$ for every $m\geq 1$ and every $o\in \Vcal(t)$. Moreover, every virtual arc lies in an adhesion set such that $A$ is non-boring on the corresponding arc. This implies that $k\leq K \varepsilon n$. We conclude that

\[
|\Wcal (n_0,\dots n_k)| \leq (t_2 t_3)^{K\varepsilon n } r^{n-k}.
\]

Every $A \in \Scal(c,\varepsilon,n)$ is uniquely determined by some $W \in \Wcal(n_0,\dots,n_k)$ for some $k \leq K \varepsilon n$ where $n_0, \dots, n_k$ are given by the positions of the $k$ virtual arcs in $P(t)$. We conclude that

\[
\abs{ \mathcal{S}(c,\varepsilon,n)} \leq \sum_{k=0}^{\lfloor K\varepsilon n \rfloor} \binom{n}{k} (t_2 t_3)^{K\varepsilon n } r^{n-k}.
\]

Using Stirling's approximation as in (<ref>) and the fact that the binomial coefficients $\binom{n}{k}$ are monotonic in $k$, we see that

\[
\binom{n}{k}\leq \left(\frac{1}{(K\varepsilon)^{K\varepsilon}(1-K\varepsilon)^{1-K\varepsilon}}\right)^{n+o(n)}
\]

for every $0\leq k \leq K \varepsilon n$ and every $0<\varepsilon\leq \frac{1}{2K}$. Therefore, for some positive constant $t_4$ depending on $t_1$, $t_2$, $t_3$ and $K$,

\[
\Sigma_n(R) \leq \sum_{k=0}^{\lfloor K \varepsilon n \rfloor}R^{(1-K \varepsilon) n} t_4^{\varepsilon n} r^{n-k} \left(\frac{1}{(K\varepsilon)^{K\varepsilon}(1-K\varepsilon)^{1-K\varepsilon}}\right)^{n+o(n)}.
\]

It is possible to choose $0<\varepsilon\leq \frac{1}{2K}$ to be small enough so that

\[
\frac{2^{\varepsilon} t_4^{\varepsilon} r^{1-k/n}}{R^{K\varepsilon}(K\varepsilon)^{K\varepsilon}(1-K\varepsilon)^{1-K\varepsilon}} \leq  \frac{1}{R}
\]

holds for $n$ large enough because the left side goes to $r$ as $\varepsilon$ tends to $0$. Hence, we obtain

\[
\Sigma_n(R) \leq (K\varepsilon n +1) R^{(1-K \varepsilon) n} 2^{-\varepsilon n} R^{K\varepsilon n} R^{-n+o(n)} \leq 2^{-\varepsilon n+o(n)},
\]

as desired.

Let us next bound $\Lambda_n^1(R)$.
Our aim is to estimate $\sum_{(A_e)\in \mathcal{M}(A,\varepsilon,n,L_0)} R^{\norm{(A_e)}}$ for a certain length $L_0$. Let $p=2^{-{4/\varepsilon}}$ and note that there exist a constant $L_0>0$ such that

\[
\sum_{\substack{A \; c'\text{-completion}\\\norm{A}\geq L_0}} R^{\norm{A}}\leq p F_{c'}(R).
\]

for every $c'\in \Ucal$.

For a fixed $H \subseteq \nb(A,t)\setminus \{x\}$ with $|H| \geq \varepsilon n/2$, we have

\[
\sum_{\substack{(A_e)\in \mathcal{M}(A,\varepsilon,n,L_0)\\ \norm{A_e}\geq L_0 \text{ for } e \in H}} R^{\norm{(A_e)}} \leq p^{\varepsilon n/2} \prod_{e \in \nb(A,t) \setminus\{x\}}F_{C(e)}(R).
\]

Each $(A_e)\in \mathcal{M}(A,\varepsilon,n,L_0)$ by definition satisfies $\norm{A_e}\geq L_0$ for at least $\varepsilon n/2$ arcs $e\in E(S)\setminus \{x\}$. Summing over all possible $H$ yields

\[
\sum_{(A_e)\in \mathcal{M}(A,\varepsilon,n,L_0)} R^{\norm{(A_e)}}\leq
2^n p^{\varepsilon n/2} \prod_{e \in \nb(A,t) \setminus\{x\}}F_{C(e)}(R).
\]

It follows that

\begin{equation*}
\begin{split}
\Lambda_n^1(R) \leq  2^n p^{\varepsilon n/2} \sum_{A\in \mathcal{L}(c,\varepsilon,n)} R^{\norm{A}} \prod_{e \in \nb(A,t) \setminus\{x\}}F_{C(e)}(R) \leq 2^n p^{\varepsilon n/2}  F_c(R) \leq 2^{-n}F_c(R).
\end{split}
\end{equation*}

Finally we find an upper bound for $\Lambda_n^2(R)$. To this end, we employ a similar strategy as in Lemma <ref>.

For $e_0 \in E(T)$, Proposition <ref> yields an arc $f_0 \in E(K_{e_0})$ in the orbit of $\bar e_0$ such that $e_0$ and $f_0$ are linkable. Let $M=d_G(\Vcal(e_0),\Vcal(f_0))$ and let $M'= d_T(e_0,f_0)$. We choose $f_0$ such that that $M > L_0$.

For a $c$-completion $A = (P,C)$, we denote by $A_S$ and $A_e$ the restrictions of $A$ to $S$ and $K_{\bar e}$, respectively. Assume that we are given a $c$-completion $A$ such that $A_S \in \mathcal{L}(c,\varepsilon,n)$ and $(A_e)_{e\in E(S)\setminus \{x\}}\in \mathcal{F}(A,\varepsilon,n,L_0)$ and let $w=\varphi(A)$ be the walk represented by $A$. Consider the set of arcs $e\in \nb(A,t) \setminus \{x\}$ such that $\norm{A_e}< L_0$. As in the proof of Lemma <ref> we can find a subset $\Bcal(w)$ of these arcs of size at least $m := \lfloor\varepsilon' n \rfloor$ for some $0<\varepsilon'<\varepsilon/2$ such that $d_G(\Vcal(e),\Vcal(f)) > 2 M+ 2 D$ for distinct $e,f \in \Bcal(w)$, where $D$ is the diameter of the adhesion sets. Indeed, at least $\varepsilon n/2$ vertices of the walk $w$ lie in adhesion sets $\Vcal(e)$ for $e\in \nb(A,t) \setminus \{x\}$ such that $\norm{A_e}< L_0$, and the $(2M+2D)$-ball around each such vertex covers only a constant number of other vertices.

Let $\varepsilon''\in (0,1)$ be a constant to be defined.
Consider a subset $H$ of $\Bcal(w)$ of cardinality $k:=\lfloor \varepsilon'' m \rfloor$. Each $e\in H$ either lies in the orbit of $e_0$ or in the orbit of $f_0$. If there is $\gamma \in \Gamma$ such that $\gamma e_0 = e$, then we choose $f(e,w) = \gamma f_0$. Otherwise there is $\gamma \in \Gamma$ such that $\gamma f_0 = e$ and we choose $f(e,w) = \gamma e_0$.
Note that $M > L_0$ and the choice of $e$ such that $\norm{A_e} < L_0$ implies that $0 < d_G(w,\Vcal(f(e,w))) < M+D$. Choose a vertex $u_e=u_e(w)$ of $w$ such that $d_G(u_e,\Vcal(f(e,w)))=d_G(w,\Vcal(f(e,w)))$. The walk $w$ induces an order on the vertices $\{u_e\mid e \in H\}$, denote them by $u_1, \dots, u_k$. This order induces an order on $H$, denoted by $e_1,\dots,e_k$, and consequently also on the arcs $\{f(e,w)\mid e \in H\}$ which we denote by $f_1, \dots, f_k$. As in Lemma <ref>, we successively apply Construction <ref> to $w$. Let $w_1(H) \in \refl_{f_1}(w)$ be a reflection-extension of $w$ through $f_1$ with splitting point $u_1$ and let $g_1$ be the automorphism applied to the second part of $w$ in the reflection-extension process.

Consider the second element $f_2\in H$, and note that $g_1(u_2)$ minimizes $d_G(v, \Vcal(g_1(f_2)))$ among the vertices $v$ of $w_1(H)$, since

\[
\]

Thus there is a reflection-extension $w_2(H) \in \refl_{g_1(f_2)}(w_1(H))$ of $w_1(H)$ through $g_1(f_2)$ with splitting point $g_1(u_2)$. Continuing in this way, we obtain a sequence of SAWs $w_1(H),\ldots,w_k(H)$.

Letting $H$ vary over all possible subsets of $\Bcal(w)$ of cardinality $k$, we obtain a map $(w,H) \mapsto w_k(H)$. We claim that this map is injective. Indeed, note first that the set $H$ can be reconstructed uniquely from $w_k(H)$. The arc $e_1$ is the unique arc in $\Eout(t)$ such that the configuration defined by $w_k(H)$ on $e_1$ is an I-configuration. Then, up to orientation, $f_1$ is the unique arc of $K_{\bar e_1}$ such that $d_G(\Vcal(e_1),\Vcal(f_1))=M$ and $w_k(H)$ visits $\Vcal(f_1)$. This also defines uniquely the map $g_{1}$ used in the reflection-extension process. Similarly $g_1(e_2)$ is the unique arc in $\Eout(g_1(t)) \setminus \{e_1\}$ such that the configuration defined by $w_k(H)$ on $g_1(e_2)$ is an I-configuration. Proceeding in this way, we see that $H$ is uniquely given by $w_k(H)$. But then the claim is a consequence of Lemma <ref>.

Note that each time we apply the local modification, the length of the SAW we obtain increases by at most $\ell$, where $\ell>0$ is a uniform constant, hence $\abs{w_k(H)}\leq \abs{w}+k\ell$. Therefore,

\[
\Lambda_n^2(R) = \sum_{A\in \mathcal{L}(c,\varepsilon,n)} \sum_{(A_{e})\in \mathcal{F}(A,\varepsilon,n,L)} R^{\abs{w}} \leq \frac{1}{\binom{m}{k}R^{k\ell} } \sum_{(w,H)} R^{\abs{w_k(H)}}.
\]

where the sum index $(w,H)$ ranges over the set of all walks $w$ represented by a $c$-completion $A$ such that $A_S \in \mathcal{L}(c,\varepsilon,n)$ and $(A_e)_{e\in E(S)\setminus \{x\}}\in \mathcal{F}(A,\varepsilon,n,L_0)$, and all possible choices of subsets $H$ of $\Bcal(w)$ of size $k$.

Each walk $w_k(H)$ is a self-avoiding walk starting at $\Vcal(x)$, and ending at $\Vcal(x')$, where $x'=(g_k \circ \dots \circ g_1)(x)$. Note that $g_1, \dots, g_k$, and thus also $x'$, depend on $H$. By Theorem <ref> there is a representation $A_H=(P_H,C_H)$ of $w_k(H)$ such that $X_H(x)=x$ and $Y_H(x')=x'$. Note also that by construction $C_H(x)$ and $C_H(x')$ are simple configurations because $w$ meets $\Vcal(x)$ only in its endpoints. Observe that the distance of $x$ and $x'$ is $2 k M' + k N'+k+1$ because for every $i=1, \dots, k$ the distance of $e_i$ and $f_i$ is $M'$ and the distance of $f_i$ and $g_i (f_i)$ is $N'$. Thus the arrangement $A_H$ is counted in some entry of $\Jac_p(R)^{k (2M' + N'+ 1) + 1}$. We obtain

\[
\sum_{(w,H)} R^{\abs{w_k(H)}}\leq \norm{\Jac_p(R)^{k (2M' + N'+ 1) + 1}}_1 \leq e^{t_5 k}
\]

for some constant $t_5$.

Using the bound (<ref>) for the binomial coefficient, we see that we can choose $\varepsilon''$ small enough so that

\[
\Lambda_n^2(R) \leq \frac{e^{t_5k}}{\binom{m}{k}R^{k\ell} } \leq e^{-\varepsilon'' m+o(m)},
\]

Since $m = \lfloor \varepsilon' n \rfloor$, the desired assertion follows readily.

Proposition <ref> can be now proved in a similar way.

For $c,c'\in \Ical_p$, the analyticity of $\Jac_{c,c'}(z,\ybf)$ can be proved by arguing as in Proposition <ref>. Indeed, we can split $\Phi_n(R)$ into three sums $\Sigma_n(R)$, $\Lambda^1_n(R)$ and $\Lambda^2_n(R)$, where each of them can be handled in the same way. We emphasise that this is indeed the case for $\Lambda^2_n(R)$ because of our assumption that $c,c'\in \Ical_p$, which allows us to obtain an arrangement that contributes to $\Jac_p(R)^N$, for some $N>0$, after applying a successive application of our construction.

In general, for $c=(q,x,y),c'=(q',x',y')\in \Ical$, we can see that $c$ and $c'$ contain simple configurations $c_1=(q_1,x,y)$ and $c_1'=(q_1',x',y')$ and U-configurations $c_2=(q_2,x,x),c_2'=(q_2', \bar{x}',\bar{x}')$.

Then for $(z,\ybf)=((1+\delta)R,(1+\delta)\Fbf(R))$

\[\Jac_{c,c'}(z,\ybf)\leq \Jac_{c_1,c'_1}(z,\ybf) P_{c_2}(z,\ybf) P_{c_2'}(z,\ybf),\]
and each term in the product is finite for some $\delta>0$ sufficiently small.

§ SPECTRAL RADIUS AND RADIUS OF CONVERGENCE

Our goal in this section is to show that $R < r_\Kcal$ for every U-component $\Kcal$. Our approach loosely follows Alm and Janson [1] of decomposing U-configurations into smaller U-configurations and pairs of I-configurations. In order to formalise this approach we first need a few definitions.

A pair configuration is a pair $(c_1,c_2)$ of persistent I-configurations $c_1=(q_1,x_1,y_1), c_2=(q_2,x_2,y_2) \in \Ical_p$ such that $x_1 = x_2$; we write  $\Ical_\pair=\{(c_1,c_2) \in \Ical_p \times \Ical_p: {x_1}={x_2}\}$ for the set of all pair configurations.

Let $(c_1,c_2)$ and $(c_1',c_2')$ be pair configurations.
A $(c_1,c_2)$–$(c_1',c_2')$-completion is a pair $(A_1,A_2)$ consisting of a $c_1$–$c_1'$-completion $A_1$ and a $c_2$–$c_2'$-completion $A_2$ having the same target arc $f$. The length of $(A_1,A_2)$ is the length of $A_1$ (which equals the length of $A_2$) and we call it disjoint if the walks $p_1$ and $p_2$ represented by $A_1$ and $A_2$ are disjoint. Denote by $\Acal(c_1,c_2,c_1',c_2',n)$ the set of all $(c_1,c_2)$–$(c_1',c_2')$-completions of length $n$ and by $\Acal_{\disj}(c_1,c_2,c_1',c_2',n)$ the subset of those which are disjoint. We define a matrix $\Jac_{\Ical_\pair}(z)$ with index set $\Ical_\pair \times \Ical_\pair$ entry-wise by

\[
(\Jac_{\Ical_\pair}(z))_{(c_1,c_2),(c_1',c_2')}=\sum_{(A_1,A_2) \in \Acal(c_1,c_2,c_1',c_2',1)} z^{\norm{A_1}+\norm{A_2}}.
\]