COARSE DISTINGUISHABILITY OF GRAPHS WITH SYMMETRIC GROWTH

JESÚS A. ÁLVAREZ LÓPEZ, RAMÓN BARRAL LIJÓ, AND HIRAKU NOZAWA

ABSTRACT. Let $X$ be a connected, locally finite graph with symmetric growth. We prove that there is a vertex coloring $\phi: X \to \{0,1\}$ and some $R \in \mathbb{N}$ such that every automorphism $f$ preserving $\phi$ is $R$-close to the identity map; this can be seen as a coarse geometric version of symmetry breaking. We also prove that the infinite motion conjecture is true for graphs where at least one vertex stabilizer $S_x$ satisfies the following condition: for every non-identity automorphism $f \in S_x$, there is a sequence $x_n$ such that $\lim d(x_n, f(x_n)) = \infty$.

CONTENTS

<table><tr><td>1. Introduction</td><td>1</td></tr><tr><td>2. Preliminaries</td><td>3</td></tr><tr><td>3. Construction of the coloring</td><td>4</td></tr><tr><td>4. Growth estimates</td><td>6</td></tr><tr><td>5. Examples</td><td>10</td></tr><tr><td>References</td><td>13</td></tr></table>

1. INTRODUCTION

A (not necessarily proper) vertex coloring $\phi$ of a graph is *distinguishing* if the only automorphism that preserves $\phi$ is the identity. This notion was first introduced in [4] under the name *asymmetric coloring*, where it was proved that 2 colors suffice to produce a distinguishing coloring of a regular tree. Later, Albertson and Collins [1] defined the *distinguishing number* $D(X)$ of a graph $X$ as the least number of colors needed to produce a distinguishing coloring. The problem of calculating $D(X)$ and variants thereof has accumulated an extensive literature in the last 20 years, see e.g. [2, 14, 16–18, 22] and references therein.

One of most important open problems in graph distinguishability is the Infinite Motion Conjecture of T. Tucker. Let us introduce some preliminaries: The motion $m(f)$ of a graph automorphism $f$ is the cardinality of the set of points that are not fixed by $f$. For a graph $X$ and a subset $A \subset \text{Aut}(X)$, the motion of $A$ is $m(A) = \inf\{m(f) \mid f \in A, f \neq \text{id}\}$, and the motion of $X$ is $m(X) = m(\text{Aut}(X))$. A probabilistic argument yields the following result for finite graphs.

**Lemma 1.1** (Motion Lemma, [20]). If $X$ is a finite graph and $2^{m(X)} \ge |\text{Aut}(X)|^2$, then $D(X) \le 2$.

We always have $|\text{Aut}(X)|^2 \le 2^{\aleph_0}$ when $X$ is countable, which motivates the following generalization.

**Conjecture 1.2** (Infinite motion conjecture, [22]). If $X$ is a connected, locally finite graph with infinite motion, then $D(X) \le 2$.

JESÚS A. ÁLVAREZ LÓPEZ, DEPARTAMENTO E INSTITUTO DE MATEMÁTICAS, FACULTADE DE MATEMÁTICAS, UNIVERSIDADE DE SANTIAGO DE COMPOSTELA, 15782 SANTIAGO DE COMPOSTELA, SPAIN. E-mail: jesus.alvarez@usc.es

(Corresponding author) RAMÓN BARRAL LIJÓ, RESEARCH ORGANIZATION OF SCIENCE AND TECHNOLOGY, RITSUMEIKAN UNIVERSITY, NOJIHIGASHI 1-1-1, KUSATSU-SHIGA, 525-8577, JAPAN. E-mail: ramonbarrallijo@gmail.com

HIRAKU NOZAWA, DEPARTMENT OF MATHEMATICAL SCIENCES, COLLEGES OF SCIENCE AND ENGINEERING, RITSUMEIKAN UNIVERSITY, KUSATSU-SHIGA, 525-8577, JAPAN. E-mail: hnozawa@fc.ritsumei.ac.jp

Date: January 22, 2024.

2020 Mathematics Subject Classification. 05C15, 51F30.

Key words and phrases. graph, coloring, distinguishing, coarse, growth, symmetry.
The condition of local finiteness cannot be omitted [17]; note also that every connected, locally finite graph is countable. This conjecture has been confirmed for special classes of graphs: F. Lehner proved it in [16] for graphs with growth at most $O(2^{(1-\epsilon)\sqrt{\frac{R}{2}}})$ for some $\epsilon > 0$,<fnref n="1" /> and later, together with M. Pilśniak and M. Stawiski [18], for graphs with degree less or equal to five.

The aim of this paper is to introduce a large-scale-geometric version of distinguishability for colorings, and to prove the existence of such colorings in graphs whose growth functions are large-scale symmetric. This will result in a proof of Conjecture 1.2 for graphs with a vertex stabilizer $S_x$ satisfying that, for every automorphism $f \in S_x \setminus \{\mathrm{id}\}$, there is a sequence $x_n$ such that $d(x_n, f(x_n)) \to \infty$; we can regard this condition as a geometric refinement of having infinite motion.

Let $X$ and $Y$ be connected graphs, endowed with their canonical $N$-valued<fnref n="2" /> metric. In the context of coarse geometry (see [19] for a nice exposition on the subject), two functions $f, g: X \to Y$ are $R$-close ($R \ge 0$) if $d(f(x), g(x)) \le R$ for all $x \in X$, and we say that $f$ and $g$ are *close* if they are $R$-close for some $R \ge 0$. Let $\mathrm{QI}(X)$ denote the group of closeness classes of quasi-isometries (in the sense of Gromov) $f: X \to X$, and let $\iota: \mathrm{Aut}(X) \to \mathrm{QI}(X)$ denote the natural map that sends every automorphism to its closeness class. We can adapt the notion of distinguishing coloring to this setting as follows:

**Definition 1.3.** A coloring $\phi: X \to \mathbb{N}$ is coarsely distinguishing if every $f \in \mathrm{Aut}(X, \phi)$ is close to the identity; that is, $\iota(\mathrm{Aut}(X, \phi)) = \{[\mathrm{id}_X]\}$.

This new definition begs the following question: which connected, locally finite graphs admit a coarsely distinguishing coloring by two colors? In Section 5.1 we present a simple example of a graph that does not admit such a coloring. The first main result of this paper shows that graphs with symmetric growth admit coarsely distinguishing colorings by two colors; this condition is satisfied by vertex-transitive graphs and, more generally, coarsely quasi-symmetric graphs [3, Cor. 4.17]. The intuitive ideas behind these notions are as follows: A connected, locally finite graph has the same growth type at all vertices (see Section 2). If all of those growth types can be compared using the same constants, then the graph is said to have symmetric growth (see Definition 2.2). Similarly, given any pair of vertices, there is a quasi-isometry mapping one of them to the other one. If all of those quasi-isometries can be obtained with the same distortion bounds, then the graph is called coarsely quasi-symmetric [3, Def. 3.16]. This can be thought of as the coarse-geometric analogue of being vertex-transitive.

**Theorem 1.4.** Let $X$ be a connected, locally finite graph of symmetric growth. Then there are $R \in \mathbb{N}$ and $\phi: X \to \{0, 1\}$ such that every $f \in \mathrm{Aut}(X, \phi)$ satisfies $d(x, f(x)) \le R$ for all $x \in X$.

Note that we obtain a uniform closeness parameter $R$ for all $f \in \mathrm{Aut}(X, \phi)$; furthermore, we make no assumption on the motion of the graph. A slight modification of the proof of Theorem 1.4 proves the infinite motion conjecture for graphs $X$ containing a vertex $x \in X$ such that the restriction $\iota: S_x \to \mathrm{QI}(X)$ is injective. Let us rephrase this condition in a language closer to the statement of Conjecture 1.2. Let $X$ be a connected graph and let $f \in \mathrm{Aut}(X)$. The geometric motion of $f$ is then $\mathrm{gm}(f) = \sup\{d(x, f(x)) \mid x \in X\}$; for a subset $A \subset \mathrm{Aut}(X)$, the geometric motion of $A$ is $\mathrm{gm}(A) = \sup\{\mathrm{gm}(f) \mid f \in A, f \ne \mathrm{id}\}$. The definition of the “closeness” relation for functions yields that the restriction $\iota: A \to \mathrm{QI}(X)$ is injective if and only if $\mathrm{gm}(A) = \infty$. The second main result of the paper then reads as follows.

**Theorem 1.5.** Let $X$ be a connected, locally finite graph with symmetric growth. If $m(X) = \infty$ and there exists $x \in X$ such that $\mathrm{gm}(S_x) = \infty$, then $D(X) \le 2$.

In Sections 5.3 and 5.4 we present two families of graphs satisfying the hypothesis of Theorem 1.5: the Diestel-Leader graphs $\mathrm{DL}(p, q)$, $p, q \ge 2$, and graphs with *bounded cycle length*. The origin of Diestel-Leader graphs goes back to the following question, posed in [21, 23] by W. Woess:

**Question 1.6.** Is there a locally finite vertex-transitive graph that is not quasi-isometric to the Cayley graph of some finitely generated group?

R. Diestel and I. Leader introduced in [10] the graph $\mathrm{DL}(2, 3)$, and conjectured that it satisfies the conditions of Question 1.6. A. Eskin, D. Fisher, and K. Whyte proved in [11–13] that in fact all graphs

<footnote n="1">¹The notation $f = O(g)$ is used if there are $C, N$ such that $f(x) \le Cg(x)$ for all $x > N$.</footnote>

<footnote n="2">²We will use the convention that $0 \in \mathbb{N}$.</footnote>
DL(p, q) with p ≠ q answer Question 1.6 positively. On the other hand, graphs with bounded cycle length are hyperbolic (in the sense of Gromov) and contain as examples free products of finite graphs.

A preliminary version of this paper stated that the authors did not know of any proof in the literature for the existence of distinguishing colorings by 2 colors for these families of graphs. An anonymous referee has pointed to us that, in the case of Diestel-Leader graphs, this actually follows from the fact that they satisfy the Distinct Spheres Condition (DSC) [15, Thm. 4]. A connected graph X satisfies the DSC if there is a vertex v ∈ X such that, for all distinct u, w ∈ X,

$$d(v, u) = d(v, w) \implies S(u, n) \neq S(w, n) \text{ for infinitely many } n. \quad (1)$$

Since both symmetric growth and the DCS prove the existence of distinguishing colorings by 2 colors for the same family of graphs, it is natural to ask if there is any relation between these two notions; in Section 5 we present simple examples showing that all four possible Boolean combinations of these two conditions can be realized. This shows to some extent that our results and those in [15] are independent.

We can sketch the idea behind the proofs of Theorems 1.4 and 1.5 as follows: Choose a suitable $R > 0$ and a subset $Y \subset X$ such that $d(x, Y) \le R$ for all $x \in X$. Suppose that there is a partial coloring $\psi$ by two colors such that, if $\phi: X \to \{0, 1\}$ is an extension of $\psi$ and $f$ is an automorphism of $X$ preserving $\phi$, then $f(Y) = Y$. Thus we can regard every extension $\phi$ of $\psi$ as a coloring $\bar{\phi}: Y \to \mathbb{N}$ by more than two colors. The hypothesis of symmetric growth ensures that, for $R$ large enough, we have sufficiently many local extensions of $\psi$ around every point $y \in Y$ so that, gluing them, we can find a global extension $\phi$ with $\bar{\phi}$ distinguishing. Theorems 1.4 and 1.5 then follow from a simple geometrical argument. In general, we cannot find a partial coloring $\psi$ as above, but the same idea works with minor modifications; this technique is similar to that used in [2].

The outline of the paper is as follows: In the next section we introduce some preliminaries to be used in the proof of the main theorems, which comprises Sections 3 and 4. Finally, Section 5 contains several examples illustrating some of the concepts that appear in the paper.

## 2. PRELIMINARIES

In what follows we only consider undirected, simple graphs, so there are no loops and no multiple edges. We identify a graph with its vertex set, and by abuse of notation we write $X = (X, E_X)$. The degree of a vertex $x \in X$, deg $x$, is the number of edges incident to $x$, and the degree of $X$ is deg $X = \sup\{\deg x | x \in X\}$. A graph $X$ is locally finite if $\deg x < \infty$ for all $x \in X$. A path $\gamma$ in $X$ of length $l \in \mathbb{N}$ is a finite sequence $x_0, x_1, \dots, x_l$ of vertices such that $x_{i-1}E_X x_i$ for all $i = 1, \dots, l$; when the sequence of vertices is infinite, we call $\gamma$ a *ray*. We may also think of a path (respectively, a *ray*) as a function $\sigma: \{0, \dots, n\} \to X$ (respectively, $\sigma: \mathbb{N} \to X$). A graph is *connected* if every two vertices can be joined by a path. All graphs in this paper are assumed to be connected and locally finite, hence countable. We consider every graph to be endowed with its canonical $\mathbb{N}$-valued metric, where $d(x, y)$ is the length of the shortest path joining $x$ and $y$; a length-minimizing path is termed a *geodesic path*.

A *partial coloring* of a graph $X$ is a map $\psi: Y \to \mathbb{N}$, where $Y \subset X$; if $Y = X$, we simply call $\psi$ a *coloring*. We use the term (partial) 2-*coloring* when $\psi$ takes values in $\{0, 1\}$. For every graph $X$ and coloring $\phi: X \to \mathbb{N}$, let Aut($X$, $\phi$) denote the group of automorphisms $f$ of $X$ satisfying $\phi = \phi \circ f$. A coloring $\phi: X \to \mathbb{N}$ is *distinguishing* if Aut($X$, $\phi$) = {id}.

For a graph $X$, $x \in X$, and $r \in \mathbb{N}$, let

$$D(x, r) = \{ y \in X \mid d(y, x) \le r \}, \quad S(x, r) = \{ y \in X \mid d(y, x) = r \}$$

denote the *disk* and the *sphere* of center $x$ and radius $r$, respectively. We may write $D_X(x, r)$ for $D(x, r)$ when the ambient space $X$ is not clear from context. A subset $Y$ of $X$ is *R-separated* ($R > 0$) if $d(y, y') \ge R$ for all $y, y' \in Y$ with $y \ne y'$; it is *R-coarsely dense* if, for every $x \in X$, there is some $y \in Y$ with $d(x, y) \le R$. The next result follows from a simple application of Zorn's Lemma.

**Lemma 2.1** (E.g. [2, Cor. 2.2.]). Let $X$ be a graph and let $R > 0$. For every $x \in X$, there is a $(2R + 1)$-separated, $2R$-coarsely dense subset $Y \subset X$ containing $x$.

Let $\beta_x: \mathbb{N} \to \mathbb{N}$ and $\sigma_x: \mathbb{N} \to \mathbb{N}$ be the functions defined by

$$\beta_x(r) = |D(x, r)|, \quad \sigma_x(r) = |S(x, r)|.$$
Given two non-decreasing functions $f,g: \mathbb{N} \to \mathbb{R}^+$, $f$ is dominated by $g$ if there are integers $k,l,m$ such that $f(r) \le kg(lr)$ for all $r \ge m$. Two functions have the same growth type if they dominate one another. The growth type of $\beta_x$ does not depend on the choice of point $x \in X$, so every graph has a well-defined growth type. The functions $\beta_x$, $x \in X$, however, may not dominate one another with a uniform choice of constants, which motivates the following definition.

**Definition 2.2** ([3, Def. 4.13]). A graph $X$ has symmetric growth if there are $k,l,m \in \mathbb{N}$ such that $\beta_x(r) \le k\beta_y(lr)$ for all $r \ge m$ and $x,y \in X$.

**Lemma 2.3.** If $X$ has symmetric growth, then $\deg X < \infty$.

*Proof.* Let $x \in X$, then we have $\deg y < \beta_y(1) \le k\beta_x(lm) < \infty$ for every $y \in X$. □

Let $X$ be a graph with $\Delta := \deg X < \infty$, then the following holds for all $x \in X$ and $r \ge 1$ [2, Lem. 2.12]:

$$ \sigma_x(1) \le \Delta, \qquad (2) $$

$$ \sigma_x(r+1) \le \sigma_x(r)(\Delta-1), \qquad (3) $$

$$ \sigma_x(r+1) \le \Delta(\Delta-1)^r. \qquad (4) $$

We will later fix a graph with $\Delta > 2$; note that in this case $\Delta/(\Delta-2) \le 3$, so

$$ \beta_x(r) \le 1 + \Delta \sum_{s=0}^{r-1} (\Delta - 1)^s = 1 + \frac{\Delta((\Delta - 1)^r - 1)}{\Delta - 2} \le 1 + 3(\Delta - 1)^r - 1 = 3(\Delta - 1)^r. \qquad (5) $$

We say that $X$ has exponential growth if $\liminf \frac{\log \beta_x(r)}{r} > 0$ for some, and hence all $x \in X$, else it has subexponential growth. The following lemmas have elementary proofs.

**Lemma 2.4.** Let $X$ be a graph with symmetric exponential growth. Then there are $k,l,m \in \mathbb{N}$ such that $e^r \le k\beta_x(lr)$ for all $x \in X$ and $r \ge m$.

**Lemma 2.5.** If $X$ has symmetric subexponential growth, then, for every $a,b > 0$, there is some $m \in \mathbb{N}$ such that $\beta_x(r) \le ae^{br}$ for all $x \in X$ and $r \ge m$.

### 3. CONSTRUCTION OF THE COLORING

Let $R$ be a large enough odd number, to be determined later. Let $Y$ be a $(2R+1)$-separated, $2R$-coarsely dense subset of $X$; we define a graph structure $E_Y$ on $Y$ as follows:

$$ yE_{Y}y' \quad \text{if and only if} \quad 0 < d(y, y') \le 4R + 1. \qquad (6) $$

**Lemma 3.1.** The graph $(Y, E_Y)$ is connected with $\deg_Y y \le |D_X(y, 4R+1)| - 1$ for all $y \in Y$.

*Proof.* The inequality follows trivially from (6), so let us prove that $Y$ is connected. Let $y, y' \in Y$, and let $(y, x_1, \dots, x_{n-1}, y')$ be a path in $X$. Since $Y$ is $2R$-coarsely dense, for every $i = 1, \dots, n$ there is some $y_i \in Y$ with $d_X(x_i, y_i) \le 2R$. The triangle inequality and (6) then yield that $(y, y_1, \dots, y_{n-1}, y')$ is a path on $(Y, E_Y)$. □

Recall that $R$ is a large enough odd number, so assume $R \ge 5$. Let

$$ A = \{2n \mid 2 \le n \le \frac{R-1}{2}\}, \quad B = \{2n+1 \mid 1 \le n \le \frac{R-1}{2}\}, \qquad (7) $$

and, for $r \le R$, let

$$ D(Y, r) = \bigcup_{y \in Y} D(y, r), \quad S(Y, r) = D(Y, r) \setminus D(Y, r-1) = \bigcup_{y \in Y} S(y, r), $$

where the last equality holds because $Y$ is $(2R+1)$-separated. Let us define a partial coloring

$$ \psi: X \setminus \bigcup_{r \in B} S(Y, r) \to \{0, 1\} $$
as follows (Cf. [9, Lem. 3.2], see Figure 1 for an illustration):

$$ \psi(x) = \begin{cases} 0, & x \in \bigcup_{r=0,1} S(Y, r), \\ 1, & x \in S(Y, 2), \\ 1, & x \in \bigcup_{r \in A} S(Y, r), \\ 1, & x \notin D(Y, R). \end{cases} \qquad (8) $$

Note that the vertices that are not colored by this formula are precisely those in $S(y, r)$ for $r \in B$.

<figure><img src="image_1.png" /><figcaption>FIGURE 1. An illustration of the coloring $\psi$, where $y_1, y_2 \in Y$, black represents the color 0, and white represents 1. The grey vertices are those where $\psi$ is not defined.</figcaption></figure>

**Lemma 3.2** (Cf. [9, Lem. 3.2.]). Let $\phi: X \to \{0, 1\}$ be an extension of $\psi$, and let $f \in \mathrm{Aut}(X, \phi)$. For each $y \in Y$, there is some $\bar{y} \in Y$ such that $d(\bar{y}, f(y)) \le 1$ and $d(z, \bar{y}) = d(z, f(y))$ for all $z \in X \setminus \{\bar{y}, f(y)\}$.

*Proof.* Let

$$ Y' = \{ z \in X \mid \phi(z') = 0 \text{ for all } z' \in D(z, 1) \}, $$

then (8) yields $Y' \subset D(Y, 1)$, and clearly $f(Y') = Y'$ for all $f \in \mathrm{Aut}(X, \phi)$. For $y \in Y$, let $\bar{y}$ be the unique vertex in $Y$ which is adjacent to $f(y)$. We have $\phi(z) = 0$ for every vertex $z \in D(f(y), 1)$ and $D(f(y), 1) \subset D(\bar{y}, 2)$, so $D(f(y), 1) \subset D(\bar{y}, 1)$ by (8). Since $D(\bar{y}, 1) \subset D(f(y), 2)$, we also get $D(\bar{y}, 1) \subset D(f(y), 1)$, and the result follows. $\square$

**Corollary 3.3.** If $X$ has infinite motion, then $f(Y) = Y$.

*Proof.* Let $f \in \mathrm{Aut}(X, \phi)$ and suppose $f(y) \ne \bar{y}$. By the previous lemma we have $D(f(y), 1) = D(\bar{y}, 1)$, so there is a non-trivial automorphism exchanging $f(y)$ and $\bar{y}$ and leaving all other vertices in $X$ fixed. This contradicts the assumption that $X$ has infinite motion. $\square$

**Remark 1.** Note that there might be automorphisms $f \in \mathrm{Aut}(X, \phi)$ with $f(Y) \ne Y$ when $m(X) < \infty$. The graph in Figure 1 provides such an example: the map $f$ that interchanges $y_1$ and $z$ and leaves the rest of vertices fixed is an automorphism preserving $\psi$, but $f(Y) \ne Y$.

Since $\mathrm{dom} \psi = X \setminus \bigcup_{r \in B} S(Y, r)$, an extension of $\psi$ to $X$ is the same thing as a coloring of $\bigcup_{r \in B} S(Y, r)$; for such an extension $\phi$, let $\bar{\phi}$ denote the induced coloring $Y \to \prod_B \mathbb{N}$ defined by

$$ \bar{\phi}(y) = (\bar{\phi}_r(y))_{r \in B}, \quad \text{where } \bar{\phi}_r(y) = |S(y, r) \cap \phi^{-1}(1)|. \qquad (9) $$

**Lemma 3.4.** If $\xi := (\xi_r)_{r \in B}: Y \to \prod_B \mathbb{N}$ is such that $\xi_r(y) \le \sigma_y(r)$ for every $y \in Y$, then there is at least one extension $\phi$ satisfying $\bar{\phi} = \xi$.
**Proof.** Since $Y$ is $(2R+1)$-separated, the spheres $S(y, r)$, $y \in Y$, $r \in B$, are pairwise disjoint. Thus we can define $\phi$ independently over each sphere $S(y, r)$ by coloring $\xi_r(y)$ vertices with the color 1 and the rest with the color 0. $\square$

**Lemma 3.5.** For each extension $\phi: X \to \{0,1\}$ of $\psi$ and every automorphism $f \in \mathrm{Aut}(X, \phi)$, there is a unique automorphism $\bar{f} \in \mathrm{Aut}(Y, \bar{\phi})$ such that $d(\bar{f}(y), f(y)) \le 1$ for all $y \in Y$.

**Proof.** Let $\bar{f}$ be defined by the formula $\bar{f}(y) = \bar{y}$, where $\bar{y} \in Y$ denotes the point given by Lemma 3.2. This point satisfies $d(\bar{f}(y), z) = d(f(y), z)$ for all $z \in X \setminus \{f(y), \bar{f}(y)\}$, so

$$d(y, y') = d(f(y), f(y')) = d(\bar{f}(y), \bar{f}(y'))$$

for every $y, y' \in Y$, $y \neq y'$. This equation and (6) yield that $\bar{f}$ is an automorphism of $Y$; moreover,

$$f(S(y, r)) = S(f(y), r) = S(\bar{f}(y), r)$$

for $r \ge 1$ by Lemma 3.2, so $\bar{f}$ preserves $\xi$ by (9). $\square$

**Proposition 3.6.** If $X$ has symmetric growth, then we can choose $R$ large enough so that $\prod_{r \in B}(\sigma_x(r)+1) > \beta_x(4R+1)$ for all $x \in X$.

In order to keep with the flow of the argument, we defer the proof of Proposition 3.6 to Section 4. Assume for the remainder of this section that $X$ has symmetric growth and that $R$ has been chosen satisfying the statement of Proposition 3.6.

**Proposition 3.7.** There is a distinguishing coloring $\xi := (\xi_r)_{r \in B}: Y \to \prod_B \mathbb{N}$ such that $\xi_r(y) \le \sigma_y(r) + 1$.

**Proof.** Choose a spanning tree $T$ for $(Y, E_Y)$ and a root $y_0 \in Y$. In order to define $\xi$, first let $\xi(y_0) = (0, \dots, 0)$. Every $y \in Y$ with $y \neq y_0$ has at most $|D_X(y, 4R+1)| - 1$ siblings in $T$ by Lemma 3.1. Using Proposition 3.6, we can define $\xi$ so that $\xi(y) \neq (0, \dots, 0)$ for all $y \neq y_0$, and every vertex is colored differently from its siblings in $T$. It can be easily checked that such a coloring is distinguishing [8, Lem. 4.1]. $\square$

**Proof of Theorem 1.4.** Lemma 3.4 and Proposition 3.7 prove the existence of some $\phi: X \to \{0,1\}$ extending $\psi$ and such that $\bar{\phi}: Y \to \mathbb{N}$ is distinguishing. By Lemma 3.5, every $f \in \mathrm{Aut}(X, \phi)$ satisfies $d(f(y), y) \le 1$ for all $y \in Y$. Since $Y$ is $2R$-coarsely dense, the triangle inequality yields $d(x, f(x)) \le 4R+1$ for all $x \in X$. $\square$

**Proof of Theorem 1.5.** Let $X$ have infinite motion and pick $x \in X$ so that $S_x$ has infinite geometric motion; Lemma 2.1 ensures that we can choose $Y$ so that $x \in Y$. Using Lemma 3.4 and Proposition 3.7, we construct a coloring $\phi: X \to \{0,1\}$ extending $\psi$ and such that $\bar{\phi}$ is distinguishing. Since $X$ has infinite motion, Corollary 3.3 yields $f(Y) = Y$ for every $f \in \mathrm{Aut}(X, \psi)$. Moreover, Lemma 3.5 and the fact that $\bar{\phi}$ is distinguishing show that $f|_Y = \mathrm{id}_Y$, so $\mathrm{Aut}(X, \phi) \subset S_x$. Since $\mathrm{gm}(S_x) = \infty$ by hypothesis, $\mathrm{gm}(\mathrm{Aut}(X, \phi)) = \infty$. But $Y$ is a $2R$-coarsely dense subset and is fixed pointwise by every automorphism $f$, so the triangle inequality yields $d(x, f(x)) \le 4R$ for all $x \in X$, a contradiction. $\square$

## 4. GROWTH ESTIMATES

In this section we assume that $X$ is a graph with symmetric growth. We will derive Proposition 3.6 from the following result:

**Proposition 4.1.** For $R$ large enough, we have $\prod_{r=3}^R (\sigma_x(r) + 1) > (\Delta - 1)[\beta_x(4R+1)]^2$ for all $x \in X$.

**Proof.** First, note that this result is trivial in the case where $X$ is a graph of symmetric subexponential growth. Indeed, since $X$ is infinite, we have $\sigma_x(r) \ge 1$ for all $x \in X$, $r \ge 0$, so

$$\prod_{r=3}^{R} (\sigma_x(r) + 1) \ge 2^{R-2} = \frac{1}{4} e^{R \log 2}. \qquad (10)$$

Using Lemma 2.5, we have that, for $R$ large enough,

$$\beta_x(4R+1) \le \frac{1}{8(\Delta-1)} e^{((4R+1)\log 2)/10} \le \frac{1}{8(\Delta-1)} e^{(R\log 2)/2} \qquad (11)$$
for every $x \in X$. Combining now (10) and (11), we get

$$ (\Delta - 1)[\beta_x(4R + 1)]^2 \le \frac{1}{8}e^{R \log 2} \le \prod_{r=3}^{R}(\sigma_x(r) + 1), $$

as desired. So, for the purposes of this proof, we will assume from now on that $X$ is a graph with symmetric exponential growth.

In order to obtain lower bounds for the function $\prod_{r=3}^{R}(\sigma_x(r)+1)$, let us consider the following optimization problem: given $\Delta, Q, R \in \mathbb{N}$ with

$$ \Delta > 2, \quad R > 3, \quad Q > \Delta^2 + R - 1, \tag{12} $$

minimize the function

$$ f(a_1, \dots, a_R) = \prod_{i=3}^{R} (a_i + 1) \tag{13} $$

for $a = (a_1, \dots, a_R) \in (\mathbb{Z}^+)^R$ satisfying

$$ a_1 \le \Delta, \tag{C1} $$

$$ a_i \le a_{i-1}(\Delta - 1), \tag{C2} $$

$$ \sum_{i=1}^{R} a_i = Q - 1 \tag{C3} $$

for $i = 1, \dots, R$.

*Claim 1.* The above problem has a minimum $(a_1, \dots, a_R)$ satisfying:

(i) $a_1 = \Delta$, and $a_2 = \Delta(\Delta - 1)$.

(ii) There is $0 \le I \le R-2$ such that the sequence $a_2, \dots, a_{2+I}$ is increasing and $a_i < \Delta(\Delta - 1)$ for $i > 2+I$.

(iii) For $3 \le i \le 2+I$, we have $a_i + 1 > (a_{i-1} - 1)(\Delta - 1)$.

Suppose that $(a_1, \dots, a_R)$ is a minimum that does not satisfy (i), let $n \in \{1, 2\}$ be the first index such that $a_n < \Delta(\Delta - 1)^{n-1}$, and let $m \ge 3$ be such that $a_m = \max\{a_i \mid i \ge 3\}$. Conditions (C1) and (C2) yield

$$ a_1 + a_2 \le \Delta + \Delta(\Delta - 1) = \Delta^2. \tag{14} $$

If $a_i = 1$ for all $i \ge 3$, then

$$ \sum_{i=1}^{R} a_i = a_1 + a_2 + \sum_{i=3}^{R} a_i \le \Delta^2 + R - 2 < Q - 1 $$

by (12), contradicting (C3); this shows that $a_m > 1$. The sequence $(a'_1, \dots, a'_R)$ given by

$$ a'_i = \begin{cases} a_i + 1 & \text{for } i = n, \\ a_i - 1 & \text{for } i = m, \\ a_i & \text{otherwise.} \end{cases} $$

still satisfies (C1)–(C3), and clearly $f(a'_1, \dots, a'_R) < f(a_1, \dots, a_R)$ since the index $n$ does not appear in (13). It follows that every minimum has to satisfy (i).

Let us prove that we can obtain a minimum satisfying both (i) and (ii). Let $(a_1, \dots, a_R)$ be a minimum, and let $s$ be a permutation of $\{1, \dots, R\}$ so that $s(1) = 1$, $s(2) = 2$, and

$$ (a'_1, \dots, a'_R) = (a_{s(1)}, \dots, a_{s(R)}) $$

satisfies (ii); it is obvious that such a permutation always exists. Since $s$ leaves the subset $\{3, \dots, R\}$ invariant and the function $f$ is symmetric in those indices, $(a'_1, \dots, a'_R)$ is also a minimum if it satisfies (C1)–(C3).

Let us prove that $(a'_1, \dots, a'_R)$ satisfies (C1)–(C3): Condition (C1) holds because $s(1) = 1$. In order to prove (C2), we begin by showing the following claim.

*Claim 2.* For every $i \in \{3, \dots, R\}$ with $a_i > a_2$, there is some $j \in \{2, \dots, R\}$ such that $j \ne i$ and $a_2 \le a_j < a_i \le (\Delta - 1)a_j$.
Let $l$ be an integer to be determined later, we are going to define a sequence of indices $m_1, \dots, m_l$ in $\{2, \dots, R\}$. Let

$$m_1 = \inf\{i \in \{2, \dots, R\} \mid a_i \ge a_j \text{ for all } 2 \le j \le R\},$$

and assume $a_{m_1} > a_2$, since otherwise the claim is vacuously true. Suppose now that, for $i > 1$, we have defined $m_j$ for $1 \le j < i$. If $a_{m_{i-1}} = a_2$, then let $l = i - 1$, so that $m_{i-1}$ is the last element in the sequence. If $a_{m_{i-1}} > a_2$, then let

$$m_i = \inf\{i \in \{2, \dots, m_{i-1}\} \mid a_i \ge a_j \text{ for all } 2 \le j \le m_{i-1}\}.$$

The claim is again vacuously true if $l = 1$, so assume $l \ge 2$. It follows easily from the definition of $m_i$ that $a_{m_{i-1}} = a_{m_{i+1}}$ for all $1 \le i < l$, and thus (C2) yields

$$a_{m_i} \le (\Delta - 1)a_{m_{i-1}} = (\Delta - 1)a_{m_{i+1}}. \qquad (15)$$

Observe that, for every $i \in \{3, \dots, R\}$ such that $a_2 < a_i$, there is some $j \in \{1, \dots, l-1\}$ such that $a_{m_{j+1}} \le a_i \le a_{m_j}$, which combined with (15) gives

$$a_{m_{j+1}} \le a_i \le a_{m_j} \le (\Delta - 1)a_{m_{j+1}}.$$

This concludes the proof of Claim 2.

We resume the proof of (C2), so let $I$ be the largest non-negative integer so that $a'_2, \dots, a'_{2+I}$ is increasing. Recall that $a'_2 = a_2$, and let $3 \le i \le 2 + I$. If $a'_i = a'_2$, then $a'_{i-1} = a'_2 = a'_i$, so (C2) is satisfied. If $a'_i > a'_2$, then by Claim 2 there is some $j \in \{2, \dots, R\}$ such that $a_2 \le a_j < a_{s(i)} \le (\Delta - 1)a_j$. Since $a_j > a_2$, we have $2 \le s^{-1}(j) \le 2 + I$ by (ii). Also, the sequence $a'_2, \dots, a'_{2+I}$ is increasing, so $a_j \le a'_{i-1}$ and therefore $a'_i \le (\Delta - 1)a'_{i-1}$. Thus Condition (C3) is satisfied because the sum $\sum_{i=1}^R a_i$ is invariant by permutations, and we have obtained a minimum $(a'_1, \dots, a'_R)$ that satisfies (i) and (ii).

Finally, suppose that $(a_1, \dots, a_R)$ is a minimum satisfying (i) and (ii), but not (iii). Let $n$ be an index such that $3 \le n \le R - 1$ and $a_n + 1 \le (a_{n-1} - 1)(\Delta - 1)$, then one can easily check that the solution $(a'_1, \dots, a'_R)$ given by

$$a'_i = \begin{cases} a_i - 1 & \text{for } i = n - 1, \\ a_i + 1 & \text{for } i = n, \\ a_i & \text{otherwise.} \end{cases}$$

still satisfies (C1)-(C3). Furthermore, $a_{n+1} \ge a_n$ implies $(a_{n+1} + 1)(a_n - 1) < a_{n+1}a_n$, so $f(a'_1, \dots, a'_R) < f(a_1, \dots, a_R)$, contradicting the assumption that $(a_1, \dots, a_R)$ was a minimum. This completes the proof of Claim 1.

One can easily check that, for every graph $X$ of bounded degree $\Delta$, every $x \in X$, and every $R > 3$, the sequence $(\sigma_x(1), \dots, \sigma_x(R))$ satisfies (C1)-(C3) for $Q = \beta_x(R)$. Then Claim 1 shows that, for every $x \in X$, there is a sequence $(a_{x,1}, \dots, a_{x,R})$ satisfying Claim 1(i)-(iii) for $Q = \beta_x(R)$ and such that

$$\prod_{r=3}^{R} (\sigma_x(r) + 1) \ge \prod_{r=3}^{R} (a_{x,r} + 1) \qquad (16)$$

Fix such a sequence $a_{x,r}$ for every point $x \in X$. Now (14) and Claim 1(ii) yield

$$\begin{aligned} \sum_{r=3}^{2+I} a_{x,r} &= \sum_{r=1}^{R} a_{x,r} - \sum_{r=3+I}^{R} a_{x,r} - \sum_{r=1}^{2} a_{x,r} \\ &\ge \beta_x(R) - (R - 2 - I)\Delta(\Delta - 1) - \Delta^2 \\ &\ge \beta_x(R) - R\Delta(\Delta - 1) - (\Delta - 1)^2. \end{aligned} \qquad (17)$$

By (C2), we have $a_{x,2+r} \le a_{x,2}(\Delta - 1)^r$ for $r = 1, \dots, I$, so

$$\sum_{r=3}^{2+I} a_{x,r} \le \sum_{r=1}^{I} a_{x,2}(\Delta - 1)^r = a_{x,2}(\Delta - 1) \frac{(\Delta - 1)^I - 1}{\Delta - 2} \le a_{x,2}\Delta(\Delta - 1)^I \le \Delta^3(\Delta - 1)^I. \qquad (18)$$

Since $X$ has symmetric exponential growth, by Lemma 2.4 we have

$$R\Delta(\Delta - 1) + (\Delta - 1)^2 < \beta_x(R)/2$$
for $R$ large enough and all $x \in X$, so

$$ \sum_{r=3}^{2+I} a_{x,r} \geq \beta_x(R)/2 \qquad (19) $$

by (17), and now (18) and (19) yield

$$ (\Delta - 1)^I \geq \beta_x(R)/2\Delta^3. \qquad (20) $$

From Claim 1(iii) we obtain by induction the following inequality for $r = 1, \dots, I$.

$$ \begin{aligned} a_{x,2+r} &\geq a_{x,2}(\Delta - 1)^r - 1 - 2 \sum_{i=1}^{r-1} (\Delta - 1)^i \\ &\geq a_{x,2}(\Delta - 1)^r - 1 - 2(\Delta - 1) \frac{(\Delta - 1)^{r-1} - 1}{\Delta - 2} \\ &\geq (\Delta - 1)^r (a_{x,2} - \frac{2}{\Delta - 2}) - 1. \end{aligned} $$

Since $a_{x,2} = \Delta(\Delta - 1) > 2/(\Delta - 2) + 1$, we have

$$ a_{x,2+r} \geq (\Delta - 1)^r. $$

Letting $C = 1/2\Delta^3$, (20) yields

$$ \prod_{r=3}^{R} (a_{x,r} + 1) \geq \prod_{r=3}^{2+I} (a_{x,r} + 1) \geq \prod_{r=1}^{I} (\Delta - 1)^r = ((\Delta - 1)^{I+1})^{I/2} \geq [C\beta_x(R)]^{(\log\Delta - 1)C\beta_x(R))/2. \quad (21) $$

Since $X$ has symmetric exponential growth, by Lemma 2.4 there are $k, l, m \in \mathbb{N}$ such that $k\beta_x(ln) \geq e^n$ for all $x \in X$ and $n \geq m$. So, if $R \geq lm$, then (21) yields

$$ \prod_{r=3}^{R} (a_{x,r} + 1) \geq (Ck^{-1}e^{\lfloor R/l \rfloor})^{(\lfloor R/l \rfloor + \log Ck^{-1})/2}. $$

Since $(Ck^{-1}e^{\lfloor R/l \rfloor})^{(\lfloor R/l \rfloor + \log Ck^{-1})/2}$ grows faster than $\Delta^{8R+7}$, we can assume that $R$ is large enough so that

$$ \prod_{r=3}^{R} (a_{x,r} + 1) > \Delta^{8R+7} $$

for all $x \in X$. Noting that $(\Delta - 1)^2 > 3$, equations (5) and (16) yield

$$ \prod_{r=3}^{R} (\sigma_x(r) + 1) \geq \prod_{r=3}^{R} (a_{x,r} + 1) \Delta[(\Delta - 1)^{4R+3}]^2 \geq (\Delta - 1)[\beta_x(4R + 1)]^2. \quad \square $$

*Proof of Proposition 3.6.* The definitions of $A$ and $B$ in (7) yield

$$ \prod_{r=3}^{R} (\sigma_x(r) + 1) = \left[ \prod_{r \in A} (\sigma_x(r) + 1) \right] \left[ \prod_{r \in B} (\sigma_x(r) + 1) \right]. \qquad (22) $$

We have $r - 1 \in B$ for every $r \in A$, so

$$ \prod_{r \in A} (\sigma_x(r) + 1) \leq (\Delta - 1) \prod_{r \in B} (\sigma_x(r) + 1) \qquad (23) $$

because $\sigma_x(r) \leq (\Delta - 1)\sigma_x(r - 1)$ by (3). The combination of (22) and (23) then yields

$$ \prod_{r \in B} (\sigma_x(r) + 1) \geq \sqrt{\frac{\prod_{r=3}^{R} (\sigma_x(r) + 1)}{\Delta - 1}}, $$

and the result follows from Proposition 4.1. $\square$
## 5. EXAMPLES

**5.1. A connected, locally finite graph with no coarsely distinguishing 2-coloring.** For $n \in \mathbb{Z}^+$, let $I_n = \{v_0, \dots, v_n\}$ be a graph with edges $\{v_m, v_{m+1}\}$ for $m = 0, \dots, n-1$, and let $X = \{u_m\}_{m=1}^\infty$ be a graph with edges $\{u_m, u_{m+1}\}$ for $m \in \mathbb{Z}^+$. For every $n \in \mathbb{Z}^+$, take $2^n + 1$ copies of $I_n$ and denote them by

$$I_n^i = \{v_m^i | i = 0, \dots, n\}, \quad i = 1, \dots, 2^n + 1.$$

For every $n$ and $i$, glue the graph $I_n^i$ to $X$ by identifying the points $u_n$ and $v_0^i$; denote the resulting graph by $Y$ (see Figure 2), and let $Y_n$ be the full subgraph whose vertex set is the image of $\cup_i I_n^i$ by the quotient map.

<figure><img src="image_2.png" /><figcaption>FIGURE 2. A graph without coarsely distinguishing 2-colorings</figcaption></figure>

Let $\phi$ be an arbitrary 2-coloring of $Y$. Since we have $2^n + 1$ copies of $I_n$ glued to $u_n$ ($n \in \mathbb{Z}^+$), by the pigeonhole principle there are at least two indices $i(n) \neq j(n)$ such that the restrictions of $\phi$ to $I_n^{i(n)}$ and $I_n^{j(n)}$ are equal. So there exists an isomorphism $f_n$ of $Y_n$ that preserves $\phi$ and maps $I_n^{i(n)}$ to $I_n^{j(n)}$, and therefore $d(f(v_n^{i(n)}), v_n^{j(n)}) = 2n$. Choose such an isomorphism $f_n$ for every $n \in \mathbb{Z}^+$, and combine them into an isomorphism $f$ of $Y$ preserving $\phi$. Since $d(f(v_n^{i(n)}), v_n^{j(n)}) = 2n$ for all $n \in \mathbb{Z}^+$, the map $f$ is not close to the identity. Note that the vertex $u_n$ has degree $4+2^n$, so $\deg Y = \infty$ and hence $Y$ does not have symmetric growth.

**5.2. Graphs with infinite motion but finite geometric motion.** Perhaps the simplest example of a connected locally finite graph $X$ with $m(X) = \infty$ and $gm(X) < \infty$ is shown in Figure 3. This graph has symmetric linear growth. The only non-trivial automorphism $f$ is the obvious one interchanging the horizontal rays starting at $y$ and $z$, and it is easy to check that $d(x, f(x)) \le 1$ for all $x \in X$.

<figure><img src="image_3.png" /><figcaption>FIGURE 3. Example of a graph $X$ with $m(X) = \infty$ and $gm(X) < \infty$</figcaption></figure>

We can modify this example to obtain graphs with infinite motion, finite geometric motion, and faster growth. For example, let $T_3$ be the regular tree of degree 4, and let $\phi: T_3 \to \{0, 1\}$ be an distinguishing coloring. Substitute each edge in $T_3$ by a “gadget” depending on the colors of the incident vertices (see Figure 4). In this way we obtain a graph $Y$ with $Aut(Y) = \{id_Y\}$ and symmetric exponential growth. Moreover, we can identify $T_3$ with the subset $\bar{Y}$ of $Y$ consisting of vertices of degree 4. Gluing one copy of $X$ to each vertex $y \in \bar{Y}$ by identifying it with $x$, we obtain a graph with infinite motion, finite geometric motion, and exponential (but not symmetric) growth.
<figure><img src="image_4.png" /><figcaption>FIGURE 4. Substituting each edge in $T_4$ by a graph</figcaption></figure>

5.3. **Diestel-Leader Graphs.** The Diestel-Leader graphs DL($p_1, \dots, p_n$) are defined for $n, p_1, \dots, p_n \ge 2$. For the sake of simplicity, however, we will restrict our attention to the case $n = 2$; at any rate, the following discussion can be easily adapted to include the case $n > 2$. In order to define DL($p, q$), let $T_p$ and $T_q$ be the regular trees of degree $p+1$ and $q+1$, respectively. For $i = p, q$, choose a root $o_i \in T_i$ and fix an end $\omega_i$ of $T_i$. These choices induce height or Busemann functions $h_i: T_i \to \mathbb{Z}$, and then

$$ \mathrm{DL}(p, q) := \{ (x, y) \in T_p \times T_q \mid h_p(x) + h_q(y) = 0 \}. $$

Let us $(x, y) \in \mathrm{DL}(p, q)$ as $xy$ for the sake of clarity, and let $xE_iy$ denote that $x$ and $y$ are adjacent in $T_i$, then the graph structure $E$ in $\mathrm{DL}(p, q)$ is defined by

$$ xyEx'y' \quad \text{if and only if} \quad xE_px' \text{ and } yE_qy'. $$

This yields

$$ d_{\mathrm{DL}(p,q)}(xy, x'y') \ge \max\{d_{T_p}(x, x'), d_{T_q}(y, y')\} \ge \max\{|h(x) - h(x')|, |h(y) - h(y')|\}. \quad (24) $$

For $i = p, q$, let $\mathrm{Aff}(T_i)$ be the subgroup of automorphisms of $T_i$ that fix $\omega_i$. For every $f \in \mathrm{Aff}(T_i)$, the quantity $h(f(x)) - h(x)$ is independent of $x \in T_i$, and we will denote it by $h(f)$. Let

$$ \mathcal{A}_{p,q} = \{ (f, f') \in \mathrm{Aff}(T_p) \times \mathrm{Aff}(T_q) \mid h_p(f) + h_q(f') = 0 \}. $$

**Lemma 5.1** ([5, Thm. 2.7.], [6, Prop. 3.3]). If $p \ne q$, then $\mathrm{Aut}(\mathrm{DL}(p, q)) \cong \mathcal{A}_{p,q}$. For $p = q$, the group $\mathrm{Aut}(\mathrm{DL}(p, p))$ is generated by $\mathcal{A}_{p,p}$ and the map $\sigma: xy \mapsto yx$.

Let us prove that $\mathrm{DL}(p, q)$ satisfies the hypothesis of Theorem 1.5.

**Lemma 5.2.** The group $\mathrm{Aut}(\mathrm{DL}(p, q))$ has infinite motion, and the stabilizer $S_{o_p o_q}$ has infinite geometric motion.

*Proof.* Let $a = (f, f') \in \mathcal{A}_{p,q}$. If $a \ne \mathrm{id}$, then at least one of $f, f'$ is non-trivial, say $f$. Therefore $f$ is a non-trivial automorphism of a regular tree, hence $m(f) = m(a) = \infty$. If moreover $a \in S_{o_p o_q}$, then $f(o_p) = o_p$, and therefore $\mathrm{gm}(f) = \infty$ when considered as an automorphism of $T_p$ (it is elementary to check that stabilizers in regular trees have infinite geometric motion). Now (24) yields $\mathrm{gm}(a) = \infty$, proving the result when $p \ne q$ by Lemma 5.1.

If $p = q$, then every automorphism which is not in $\mathcal{A}_{p,q}$ can be written as $\sigma a$, where $a = (f, f') \in \mathcal{A}_{p,p}$ and $\sigma$ is the map $xy \mapsto yx$. Since $f(o_p) = f'(o_p) = o_p$, we have $h(f) = h(f') = 0$. Let $x_n y_n$ be a sequence in $\mathrm{DL}(p, p)$ with $h_p(x_n) = -h_p(y_n) = n$. Then

$$ d(x_n y_n, \sigma a(x_n y_n)) = d(x_n y_n, f'(y_n) f(x_n)) \ge |h_p(x_n) - h_p(f'(y_n))| = |h_p(x_n) - h_p(y_n) - h_p(f)| \ge 2n - h_p(f), \\ \text{so } \mathrm{gm}(a) = m(a) = \infty. \quad \square $$

5.4. **Graphs with bounded cycle length.** A cycle of length $n \in \mathbb{N}$ in a graph is a path $\sigma$ of length $n$ with $\sigma(0) = \sigma(n)$ and $\sigma(i) \ne \sigma(j)$ for $0 \le i < j < n$. A graph $X$ has bounded cycle length if there is $L \in \mathbb{N}$ such that every cycle in $X$ has length $\le L$. It is not difficult to prove that all graphs of bounded cycle length are hyperbolic in the sense of Gromov. There are in the literature several non-equivalent definitions of the free product of graphs, see e.g. [7]; one can easily check, however, that the following result holds for any of the definitions: The free product of a finite family of graphs of bounded cycle length has bounded cycle length. In particular, the free product of a finite family of finite graphs has bounded cycle length.
**Lemma 5.3** (Cf. [16, Lem. 3.6]). Let $X$ be a connected locally finite graph with infinite motion, let $x \in X$, and let $f \in S_x$. Then there is a ray $\gamma: \mathbb{N} \to X$ such that $\gamma(0) = f(\gamma(0))$ and $\mathrm{im}(\gamma) \cap \mathrm{im}(f \circ \gamma) = \{\gamma(0)\}$.

*Proof.* See the proof of [16, Lem. 3.6]. □

**Proposition 5.4.** If $X$ has infinite motion and bounded cycle length, then every vertex stabilizer has infinite geometric motion.

*Proof.* Let $x \in X$ and let $f \in S_x$. By Lemma 5.3, there is a ray $\gamma$ such that, if we let $\gamma' = f(\gamma)$, then $\gamma(0) = \gamma'(0)$ and $\mathrm{im}(\gamma) \cap \mathrm{im}(\gamma') = \{\gamma(0)\}$. For $n \in \mathbb{Z}^+$, choose geodesic paths $\sigma_n$ from $\gamma(n)$ to $\gamma'(n)$. Let $m_n$ be the largest integer such that $\sigma_n(m_n) \in \mathrm{im} \gamma$, and let $m'_n$ be the least integer such that $\sigma_n(m'_n) \in \mathrm{im} \gamma'$; clearly $m_n, m'_n \le d(\gamma(n), \gamma'(n))$. The triangle $Z_n$ with sides

$$ (\gamma(0), \dots, \gamma(i) = \sigma(m_n)), \quad (\sigma(m_n), \sigma(m_n+1), \dots, \sigma(m'_n)), \quad \text{and} \quad (\gamma'(j) = \sigma(m'_n), \gamma'(j-1), \dots, \gamma'(0)) $$

determines a cycle of length $\ge 2n - 2d(\gamma(n), \gamma'(n))$. Now the assumption that $X$ has bounded cycle length yields $\lim d(\gamma(n), \gamma'(n)) = d(\gamma(n), f(\gamma(n))) = \infty$, and the result follows. □

**5.5. Symmetric growth and the distinct spheres condition.** In this section we show, using examples and a short argument, that all four possible Boolean combinations of the conditions “having symmetric growth” and “satisfying the DSC” can be realized in very simple graphs. Recall that $X$ satisfies the DSC if there is a vertex $v \in X$ such that, for all distinct $u, w \in X$,

$$ d(v, u) = d(v, w) \implies S(u, n) \neq S(w, n) \text{ for infinitely many } n. \quad (25) $$

<figure><img src="image_5.png" /><figcaption>FIGURE 5. We substitute a vertex $x$ by two copies $x_1, x_2$ with the same sphere of radius one</figcaption></figure>

We will begin by showing how to modify a graph $X$ to obtain a similar graph $X'$ that does not satisfy the DSC. Let $X$ be any connected graph, and take two different points $x, y \in X$. Using the substitution shown in Figure 5 on $x$ and $y$, we can obtain a graph $X'$ that has two pairs of vertices $x_i$, and $y_i$ ($i = 1, 2$), instead of $x$ and $y$, and so that, for any points $u, v \in X$ with $u, v \neq x, y$,

$$ d_{X'}(x_i, u) = d_X(x, u), \quad d_{X'}(y_i, u) = d_X(y, u), \quad d_{X'}(u, v) = d_X(u, v) \quad \text{for } i=1,2, \quad (26) $$

where by abuse of notation we are identifying the points of $X \setminus \{x, y\}$ with those of $X' \setminus \{x_1, x_2, y_1, y_2\}$. It follows immediately from (26) that $X'$ shares the same coarse-geometric properties of $X$; in particular, $X'$ has symmetric growth if and only if $X$ does. Let us show that $X'$ never satisfies the DSC: Let $v \in X'$ be arbitrary, then at least one pair of the new vertices does not contain $v$, assume $v \notin \{x_1, x_2\}$. Now (26) yields that $d(v, x_1) = d(v, x_2)$, but $S(x_1, n) = S(x_2, n)$ for every $n > 0$, so $X'$ does not satisfy the DSC. This procedure can be used to obtain examples of graphs of symmetric and non-symmetric growth that do not satisfy the DSC.

Regarding graphs with symmetric growth that satisfy the DSC, as stated in the introduction, the Diestel-Leader graphs constitute a family of such examples, but even simpler examples like the Cayley graph of the integers satisfy this conditions.

Finally, as for graphs with non-symmetric growth that satisfy the DSC, let $X$ denote the (unmarked, undirected) Cayley graph of $\mathbb{Z}^2$ with respect to the generating set $\{(0, 1), (1, 0)\}$, and let $Y$ be a semi-infinite ray; that is, the vertex set of $Y$ is $\{y_i\}_{i=0}^{\infty}$ and there is an edge $y_i \sim y_{i+1}$ for every $i \ge 0$. It is elementary
to check that $X$ satisfies the DSC. Let $Z$ be the graph obtained by gluing $Y$ to $X$ by identifying $y_0$ and $(0,0)$, and let us see that $Z$ still satisfies the DSC: Let $v = (0,0)$, and let $u, w$ be distinct vertices in $Z$ with $d(v, u) = d(v, w)$. If $u, w \in X \subset Z$ (we can obviously identify $X$ and $Y$ with subsets of $Z$), then

$$S(u, n) \cap X \neq S(w, n) \cap S \quad \text{for infinitely many } n$$

because $X$ satisfies the DSC. If $u \in X$ and $w = y_i \in Y$ for some $i > 0$, then, for every $n > 0$, we have

$$y_{i+n} \in S(w, n) \quad \text{but} \quad y_{i+n} \notin S(u, n)$$

because $d(u, Y) > 0$, so $Z$ also satisfies the DSC. Moreover, since $Y$ has linear growth and $X$ has quadratic growth, it is easy to check that $Z$ has non-symmetric growth.

**Acknowledgements.** Part of this work was carried out during the tenure of a Canon Foundation in Europe Research Fellowship by B.L. H.N. is partly supported by JSPS KAKENHI Grant Number 17K14195 and 20K03620. The authors are supported by the Program for the Promotion of International Research by Ritsumeikan University. The authors are also partially supported by grants FEDER/Ministerio de Ciencia, Innovación y Universidades/AEI/MTM2017-89686-P; and Xunta de Galicia/ED431C 2019/10. We would also like to thank the anonymous referee for a careful reading of the paper.

## REFERENCES

[1] M. O. Albertson and K. L. Collins. Symmetry breaking in graphs. *Electron. J. Combin.*, 3(R18), 1996.

[2] J. A. Álvarez López and R. Barral Lijó. Limit aperiodic and repetitive colorings of graphs. arXiv:1807.09256, 2018.

[3] J. A. Álvarez López and A. Candel. *Generic coarse geometry of leaves*, volume 2223 of *Lecture Notes in Mathematics*. Springer International Publishing, 2018.

[4] L. Babai. Asymmetric trees with two prescribed degrees. *Acta Mathematica Academiae Scientiarum Hungarica*, 29:193-200, 1977.

[5] L. Bartholdi, M. Neuhauser, and W. Woess. Horocyclic products of trees. *J. Eur. Math. Soc.*, 10:771-816, 2008.

[6] D. Bertacchi. Random walks on diestel-leader graphs. *Abh. Math. Semin. Univ. Hamburg*, 71(205), 2001.

[7] M. L. Carter, S. Tornier, and G. A. Willis. On free products of graphs. arXiv:2002.10639, 2020.

[8] K. L. Collins and A. N. Trenk. The distinguishing chromatic number. *Electron. J. Combin.*, 13(R16), 2006.

[9] J. Cuno, W. Imrich, and F. Lehner. Distinguishing graphs with infinite motion and nonlinear growth. *Ars Math. Contemp.*, 7(1):201-213, 2014.

[10] R. Diestel and I. Leader. A conjecture concerning a limit of non-Cayley graphs. *J. Algebraic Combin.*, 14:17-25, 2001.

[11] A. Eskin, D. Fisher, and K. Whyte. Quasi-isometric rigidity of solvable groups. *Proceedings of the International Congress of Mathematicians 2010, ICM 2010*, 3:1185-1208, 2011.

[12] A. Eskin, D. Fisher, and K. Whyte. Coarse differentiation of quasi-isometries I: Spaces not quasi-isometric to Cayley graphs. *Ann. of Math. (2)*, 176:221-260, 2012.

[13] A. Eskin, D. Fisher, and K. Whyte. Coarse differentiation of quasi-isometries II: Rigidity for Sol and lamplighter groups. *Ann. of Math. (2)*, 177:869-910, 2013.

[14] S. Hüning, W. Imrich, J. Kloas, H. Schreber, and T. W. Tucker. Distinguishing graphs of maximum valence 3. *Electron. J. Combin.*, 26(P4.36), 2019.

[15] W. Imrich, F. Lehner, and S. Smith. Distinguishing density and the distinct spheres condition. *European J. Comb.*, 89, 2020.

[16] F. Lehner. Distinguishing graphs with intermediate growth. *Combinatorica*, 33:333-347, 2015.

[17] F. Lehner and R. G. Möller. Local finiteness, distinguishing numbers, and Tucker's conjecture. *Electron. J. Combin.*, 22(P4.19), 2015.

[18] F. Lehner, M. Pilsniak, and M. Stawiski. Distinguishing infinite graphs with bounded degrees. arXiv:1810.03932, 2018.

[19] J. Roe. *Lectures on Coarse Geometry*. Number 31 in AMS University Lecture Series. American Mathematical Society, Providence, RI, USA, 2003.

[20] A. Russell and R. Sundaram. A note on the asymptotics and computational complexity of graph distinguishability. *Electron. J. Combin.*, 5(R23), 1998.

[21] P. M. Soardi and W. Woess. Amenability, unimodularity, and the spectral radius of random walks on infinite graphs. *Math. Z.*, 205:471-486, 1990.

[22] T. W. Tucker. Distinguishing maps. *Electron. J. Combin.*, 18(P50), 2011.

[23] W. Woess. Topological groups and infinite graphs. *Discrete Math.*, 95:373-384, 1991.