ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P1.06 / 71–88
https://doi.org/10.26493/1855-3974.2354.616
(Also available at http://amc-journal.eu)
Coarse distinguishability of graphs with
symmetric growth*
Jesús Antonio Álvarez López
Departamento e Instituto de Matemáticas, Facultade de Matemáticas,
Universidade de Santiago de Compostela, 15782 Santiago de Compostela, Spain
Ramón Barral Lijó †
Research Organization of Science and Technology, Ritsumeikan University,
Nojihigashi 1-1-1, Kusatsu-Shiga, 525-8577, Japan
Hiraku Nozawa ‡
Department of Mathematical Sciences, Colleges of Science and Engineering,
Ritsumeikan Univesity, Nojihigashi 1-1-1, Kusatsu, Shiga, 525-8577, Japan
Received 5 June 2020, accepted 25 March 2021, published online 19 August 2021
Abstract
Let X be a connected, locally finite graph with symmetric growth. We prove that there
is a vertex coloring ϕ : X → {0, 1} and some R ∈ N such that every automorphism f
preserving ϕ 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 Sx satisfies the following condition: for every non-
identity automorphism f ∈ Sx, there is a sequence xn such that lim d(xn, f(xn)) = ∞.
Keywords: Graph, coloring, distinguishing, coarse, growth, symmetry.
Math. Subj. Class. (2020): 05C15, 51F30
*The authors are partially supported by the Program for the Promotion of International Research by Rit-
sumeikan University and 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.
†Corresponding author. 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.
E-mail addresses: jesus.alvarez@usc.es (Jesús Antonio Álvarez López), ramonbarrallijo@gmail.com
(Ramón Barral Lijó), hnozawa@fc.ritsumei.ac.jp (Hiraku Nozawa)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
72 Ars Math. Contemp. 21 (2021) #P1.06 / 71–88
1 Introduction
A (not necessarily proper) vertex coloring ϕ of a graph is distinguishing if the only au-
tomorphism that preserves ϕ is the identity. This notion was first introduced in [4] un-
der 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 dis-
tinguishing 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 ac-
cumulated an extensive literature in the last 20 years, see e.g. [2, 14, 16, 17, 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 graphX
and a subset A ⊂ Aut(X), the motion of A is m(A) = inf{m(f) | f ∈ A, f ̸= id}, and
the motion of X is m(X) = m(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 2m(X) ≥ |Aut(X)|2, then
D(X) ≤ 2.
We always have |Aut(X)|2 ≤ 2ℵ0 whenX 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) ≤ 2.
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−ϵ)
√
n
2 ) for some
ϵ > 0,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 distinguisha-
bility 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 Sx satisfying that, for every automorphism f ∈ Sx \ {id}, there is
a sequence xn such that d(xn, f(xn)) → ∞; 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-valued2 metric. In
the context of coarse geometry (see [19] for a nice exposition on the subject), two func-
tions f, g : X → Y are R-close (R ≥ 0) if d(f(x), g(x)) ≤ R for all x ∈ X , and we say
that f and g are close if they are R-close for some R ≥ 0. Let QI(X) denote the group
of closeness classes of quasi-isometries (in the sense of Gromov) f : X → X , and let
ι : Aut(X) → QI(X) denote the natural map that sends every automorphism to its close-
ness class. We can adapt the notion of distinguishing coloring to this setting as follows:
Definition 1.3. A coloring ϕ : X → N is coarsely distinguishing if every f ∈ Aut(X,ϕ)
is close to the identity; that is, ι(Aut(X,ϕ)) = {[idX ]}.
1The notation f = O(g) is used if there are C,N such that f(x) ≤ Cg(x) for all x > N .
2We will use the convention that 0 ∈ N.
J. A. Álvarez López et al.: Coarse distinguishability of graphs with symmetric growth 73
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 sim-
ple 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, Corollary 4.17]. The intuitive ideas behind these no-
tions 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 con-
stants, then the graph is said to have symmetric growth (see Definition 2.3). 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, Definition 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 ∈ N and ϕ : X → {0, 1} such that every f ∈ Aut(X,ϕ) satisfies d(x, f(x)) ≤ R
for all x ∈ X .
Note that we obtain a uniform closeness parameter R for all f ∈ Aut(X,ϕ); fur-
thermore, 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 graphsX containing a vertex
x ∈ X such that the restriction ι : Sx → 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 ∈ Aut(X). The geometric motion of f is then gm(f) = sup{d(x, f(x)) | x ∈ X};
for a subset A ⊂ Aut(X), the geometric motion of A is gm(A) = sup{gm(f) | f ∈
A, f ̸= id}. The definition of the “closeness” relation for functions yields that the restric-
tion ι : A → QI(X) is injective if and only if gm(A) = ∞. The second main result of the
paper therefore reads as follows.
Theorem 1.5. Let X be a connected, locally finite graph with symmetric growth. If
m(X) = ∞ and there exists x ∈ X such that gm(Sx) = ∞, then D(X) ≤ 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 DL(p, q), p, q ≥ 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 DL(2, 3) and conjectured that it
satisfies the conditions of Question 1.6. A. Eskin, D. Fisher, and K. Whyte proved in [11,
12, 13] that in fact all graphs 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
74 Ars Math. Contemp. 21 (2021) #P1.06 / 71–88
(DSC) [15, Theorem 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) =⇒ S(u, n) ̸= S(w, n) for infinitely many n. (1.1)
Since both symmetric growth and the DSC 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 ⊂ X such that d(x, Y ) ≤ R for all x ∈ X . Suppose that
there is a partial coloring ψ by two colors such that, if ϕ : X → {0, 1} is an extension of ψ
and f is an automorphism of X preserving ϕ, then f(Y ) = Y . Thus we can regard every
extension ϕ of ψ as a coloring ϕ̄ : Y → N by more than two colors. The hypothesis of sym-
metric growth ensures that, for R large enough, we have sufficiently many local extensions
of ψ around every point y ∈ Y so that, gluing them, we can find a global extension ϕwith ϕ̄
distinguishing. Theorems 1.4 and 1.5 then follow from a simple geometrical argument. In
general, we cannot find a partial coloring ψ 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 prelim-
inaries 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,EX). The degree of a vertex x ∈ X , deg x, is the number of edges incident to
x, and the degree of X is degX = sup{deg x | x ∈ X}. A graph X is locally finite if
deg x <∞ for all x ∈ X . A path γ inX of length l ∈ N is a finite sequence x0, x1, . . . , xl
of vertices such that xi−1EXxi for all i = 1, . . . , l; when the sequence of vertices is
infinite, we call γ a ray. We may also think of a path (respectively, a ray) as a function
σ : {0, . . . , n} → X (respectively, σ : N → 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 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 ψ : Y → N, where Y ⊂ X; if Y = X ,
we simply call ψ a coloring. We use the term (partial) 2-coloring when ψ takes values in
{0, 1}. For every graph X and coloring ϕ : X → N, let Aut(X,ϕ) denote the group of
automorphisms f of X satisfying ϕ = ϕ ◦ f . A coloring ϕ : X → N is distinguishing if
Aut(X,ϕ) = {id}.
For a graph X , x ∈ X , and r ∈ N, let
D(x, r) = { y ∈ X | d(y, x) ≤ r }, S(x, r) = { y ∈ X | d(y, x) = r }
denote the disk and the sphere of center x and radius r, respectively. We may write
DX(x, r) for D(x, r) when the ambient space X is not clear from context. A subset Y
J. A. Álvarez López et al.: Coarse distinguishability of graphs with symmetric growth 75
of X is R-separated (R > 0) if d(y, y′) ≥ R for all y, y′ ∈ Y with y ̸= y′; it is R-coarsely
dense if, for every x ∈ X , there is some y ∈ Y with d(x, y) ≤ R.
Lemma 2.1 (E.g. [2, Corollary 2.2.]). Let X be a graph and let R > 0. For every x ∈ X ,
there is a (2R+ 1)-separated, 2R-coarsely dense subset Y ⊂ X containing x.
Remark 2.2. The proof in [2, Corollary 2.2.] makes use of Zorn’s Lemma, but the result
can be proved for countable graphs without assuming the Axiom of Choice: First, note that
the proof in [2, Corollary 2.2.] does not require the Axiom of Choice for finite graphs.
Let X be a countable graph, and let An be an increasing and exhausting sequence of finite
subsets of X . Since we can use Lemma 2.1 with finite subsets, there is a sequence of
(2R + 1)-separated, 2R-coarsely dense subsets Sn ⊂ An. The space 2X is sequentially
compact with the topology of pointwise convergence3, so there is a convergent subsequence
Sni → S. It is now elementary to check that S is a (2R+1)-separated, 2R-coarsely dense
subset of X .
Let βx : N → N and σx : N → N be the functions defined by
βx(r) = |D(x, r)|, σx(r) = |S(x, r)|.
Given two non-decreasing functions f, g : N → R+, f is dominated by g if there are
integers k, l,m such that f(r) ≤ kg(lr) for all r ≥ m. Two functions have the same
growth type if they dominate one another. The growth type of βx does not depend on the
choice of point x ∈ X , so every graph has a well-defined growth type. The functions βx,
x ∈ X , however, may not dominate one another with a uniform choice of constants, which
motivates the following definition.
Definition 2.3 ([3, Definition 4.13]). A graphX has symmetric growth if there are k, l,m ∈
N such that βx(r) ≤ kβy(lr) for all r ≥ m and x, y ∈ X .
Lemma 2.4. If X has symmetric growth, then degX <∞.
Proof. Let x ∈ X , then we have deg y < βy(1) ≤ kβx(lm) <∞ for every y ∈ X .
Let X be a graph with ∆ := degX < ∞, then the following holds for all x ∈ X and
r ≥ 1 [2, Lemma 2.12]:
σx(1) ≤ ∆, (2.1)
σx(r + 1) ≤ σx(r)(∆− 1), (2.2)
σx(r + 1) ≤ ∆(∆− 1)r. (2.3)
We will later fix a graph with ∆ > 2; note that in this case ∆/(∆− 2) ≤ 3, so
βx(r) ≤ 1 + ∆
r−1∑
s=0
(∆− 1)s = 1 + ∆((∆− 1)
r − 1)
∆− 2
≤ 1 + 3(∆− 1)r − 1
= 3(∆− 1)r. (2.4)
We say that X has exponential growth if lim inf log βx(r)r > 0 for some, and hence all
x ∈ X , else it has subexponential growth. The following lemmas have elementary proofs.
3It is well-known that, for a countable product of compact subsets of the real line, the Tychonoff theorem can
be proved without using the Axiom of Choice.
76 Ars Math. Contemp. 21 (2021) #P1.06 / 71–88
Lemma 2.5. LetX be a graph with symmetric exponential growth. Then there are k, l,m ∈
N such that er ≤ kβx(lr) for all x ∈ X and r ≥ m.
Lemma 2.6. If X has symmetric subexponential growth, then, for every a, b > 0, there is
some m ∈ N such that βx(r) ≤ aebr for all x ∈ X and r ≥ m.
3 Construction of the coloring
LetR 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 EY on Y as follows:
yEY y
′ if and only if 0 < d(y, y′) ≤ 4R+ 1. (3.1)
Lemma 3.1. The graph (Y,EY ) is connected with degY y ≤ |DX(y, 4R+ 1)| − 1 for all
y ∈ Y .
Proof. The inequality follows trivially from (3.1), so let us prove that Y is connected. Let
y, y′ ∈ Y , and let (y, x1, . . . , xn−1, y′) be a path in X . Since Y is 2R-coarsely dense, for
every i = 1, . . . , n there is some yi ∈ Y with dX(xi, yi) ≤ 2R. The triangle inequality
and (3.1) then yield that (y, y1, . . . , yn−1, y′) is a path on (Y,EY ).
Recall that R is a large enough odd number, so assume R ≥ 5. Let
A = { 2n | 2 ≤ n ≤ R− 1
2
}, B = { 2n+ 1 | 1 ≤ n ≤ R− 1
2
}, (3.2)
and, for r ≤ R, let
D(Y, r) =
⋃
y∈Y
D(y, r), S(Y, r) = D(Y, r) \D(Y, r − 1) =
⋃
y∈Y
S(y, r),
where the last equality holds because Y is (2R + 1)-separated. Let us define a partial
coloring
ψ : X \
⋃
r∈B
S(Y, r) → {0, 1}
as follows (Cf. [9, Lemma 3.2], see Figure 1 for an illustration):
ψ(x) =

0, x ∈
⋃
r=0,1 S(Y, r),
1, x ∈ S(Y, 2),
1, x ∈
⋃
r∈A S(Y, r),
1, x /∈ D(Y,R).
(3.3)
Note that the vertices that are not colored by this formula are precisely those in S(y, r) for
r ∈ B.
Lemma 3.2 (Cf. [9, Lemma 3.2.]). Let ϕ : X → {0, 1} be an extension of ψ, and let
f ∈ Aut(X,ϕ). For each y ∈ Y , there is some ȳ ∈ Y such that d(ȳ, f(y)) ≤ 1 and
d(z, ȳ) = d(z, f(y)) for all z ∈ X \ {ȳ, f(y)}.
J. A. Álvarez López et al.: Coarse distinguishability of graphs with symmetric growth 77
Figure 1: An illustration of the coloring ψ, where y1, y2 ∈ Y , black represents the color 0,
and white represents 1. The grey vertices are those where ψ is not defined.
Proof. Let
Y ′ = { z ∈ X | ϕ(z′) = 0 for all z′ ∈ D(z, 1) },
then (3.3) yields Y ′ ⊂ D(Y, 1), and clearly f(Y ′) = Y ′ for all f ∈ Aut(X,ϕ). For
y ∈ Y , let ȳ be the unique vertex in Y which is adjacent to f(y). We have ϕ(z) = 0
for every vertex z ∈ D(f(y), 1) and D(f(y), 1) ⊂ D(ȳ, 2), so D(f(y), 1) ⊂ D(ȳ, 1)
by (3.3). Since D(ȳ, 1) ⊂ D(f(y), 2), we also get D(ȳ, 1) ⊂ D(f(y), 1), and the result
follows.
Corollary 3.3. If X has infinite motion, then f(Y ) = Y .
Proof. Let f ∈ Aut(X,ϕ) and suppose f(y) ̸= ȳ. By the previous lemma we have
D(f(y), 1) = D(ȳ, 1), so there is a non-trivial automorphism exchanging f(y) and ȳ and
leaving all other vertices in X fixed. This contradicts the assumption that X has infinite
motion.
Remark 3.4. Note that there might be automorphisms f ∈ Aut(X,ϕ) with f(Y ) ̸= Y
when m(X) < ∞. The graph in Figure 1 provides such an example: the map f that
interchanges y1 and z and leaves the rest of vertices fixed is an automorphism preserving
ψ, but f(Y ) ̸= Y .
Since domψ = X \
⋃
r∈B S(Y, r), an extension of ψ to X is the same thing as a
coloring of
⋃
r∈B S(Y, r); for such an extension ϕ, let ϕ̄ denote the induced coloring Y →∏
B N defined by
ϕ̄(y) = (ϕ̄r(y))r∈B , where ϕ̄r(y) = |S(y, r) ∩ ϕ−1(1)|. (3.4)
Lemma 3.5. If ξ := (ξr)r∈B : Y →
∏
B N is such that ξr(y) ≤ σy(r) for every y ∈ Y ,
then there is at least one extension ϕ satisfying ϕ̄ = ξ.
78 Ars Math. Contemp. 21 (2021) #P1.06 / 71–88
Proof. Since Y is (2R + 1)-separated, the spheres S(y, r), y ∈ Y , r ∈ B, are pairwise
disjoint. Thus we can define ϕ independently over each sphere S(y, r) by coloring ξr(y)
vertices with the color 1 and the rest with the color 0.
Lemma 3.6. For each extension ϕ : X → {0, 1} of ψ and every automorphism f ∈
Aut(X,ϕ), there is a unique automorphism f̄ ∈ Aut(Y, ϕ̄) such that d(f̄(y), f(y)) ≤ 1
for all y ∈ Y .
Proof. Let f̄ be defined by the formula f̄(y) = ȳ, where ȳ ∈ Y denotes the point given by
Lemma 3.2. This point satisfies d(f̄(y), z) = d(f(y), z) for all z ∈ X \ {f(y), f̄(y)}, so
d(y, y′) = d(f(y), f(y′)) = d(f̄(y), f̄(y′))
for every y, y′ ∈ Y , y ̸= y′. This equation and (3.1) yield that f̄ is an automorphism of Y ;
moreover,
f(S(y, r)) = S(f(y), r) = S(f̄(y), r)
for r ≥ 1 by Lemma 3.2, so f̄ preserves ξ by (3.4).
Proposition 3.7. If X has symmetric growth, then we can choose R large enough so that∏
r∈B(σx(r) + 1) > βx(4R+ 1) for all x ∈ X .
In order to keep with the flow of the argument, we defer the proof of Proposition 3.7 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.7.
Proposition 3.8. There is a distinguishing coloring ξ := (ξr)r∈B : Y →
∏
B N such that
ξr(y) ≤ σy(r) + 1.
Proof. Choose a spanning tree T for (Y,EY ) and a root y0 ∈ Y . In order to define ξ, first
let ξ(y0) = (0, . . . , 0). Every y ∈ Y with y ̸= y0 has at most |DX(y, 4R+1)|− 1 siblings
in T by Lemma 3.1. Using Proposition 3.7, we can define ξ so that ξ(y) ̸= (0, . . . , 0) for
all y ̸= y0, and every vertex is colored differently from its siblings in T . It can be easily
checked that such a coloring is distinguishing [8, Lemma 4.1].
Proof of Theorem 1.4. Lemma 3.5 and Proposition 3.8 prove the existence of some ϕ : X →
{0, 1} extending ψ and such that ϕ̄ : Y → N is distinguishing. By Lemma 3.6, every
f ∈ Aut(X,ϕ) satisfies d(f(y), y) ≤ 1 for all y ∈ Y . Since Y is 2R-coarsely dense, the
triangle inequality yields d(x, f(x)) ≤ 4R+ 1 for all x ∈ X .
Proof of Theorem 1.5. Let X have infinite motion and pick x ∈ X so that Sx has infi-
nite geometric motion; Lemma 2.1 ensures that we can choose Y so that x ∈ Y . Us-
ing Lemma 3.5 and Proposition 3.8, we construct a coloring ϕ : X → {0, 1} extending
ψ and such that ϕ̄ is distinguishing. Since X has infinite motion, Corollary 3.3 yields
f(Y ) = Y for every f ∈ Aut(X,ψ). Moreover, Lemma 3.6 and the fact that ϕ̄ is distin-
guishing show that f |Y = idY , so Aut(X,ϕ) ⊂ Sx. Since gm(Sx) = ∞ by hypothesis,
gm(Aut(X,ϕ)) = ∞. 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)) ≤ 4R for all x ∈ X , a
contradiction.
J. A. Álvarez López et al.: Coarse distinguishability of graphs with symmetric growth 79
4 Growth estimates
In this section we assume that X is a graph with symmetric growth. We will derive Propo-
sition 3.7 from the following result:
Proposition 4.1. For R large enough, we have
∏R
r=3(σx(r)+1) > (∆−1)[βx(4R+1)]2
for all x ∈ 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 σx(r) ≥ 1 for all x ∈ X ,
r ≥ 0, so
R∏
r=3
(σx(r) + 1) ≥ 2R−2 =
1
4
eR log 2. (4.1)
Using Lemma 2.6, we have that, for R large enough,
βx(4R+ 1) ≤
1
8(∆− 1)
e[(4R+1) log 2]/10 ≤ 1
8(∆− 1)
e(R log 2)/2 (4.2)
for every x ∈ X . Combining now (4.1) and (4.2), we get
(∆− 1)[βx(4R+ 1)]2 ≤
1
8
eR log 2 ≤
R∏
r=3
(σ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
∏R
r=3(σx(r) + 1), let us consider the
following optimization problem: given ∆, Q,R ∈ N with
∆ > 2, R > 3, Q > ∆2 +R− 1, (4.3)
minimize the function
f(a1, . . . , aR) =
R∏
i=3
(ai + 1) (4.4)
for a = (a1, . . . , aR) ∈ (Z+)R satisfying
a1 ≤ ∆, (C1)
ai ≤ ai−1(∆− 1), (C2)
R∑
i=1
ai = Q− 1 (C3)
for i = 1, . . . , R.
Claim 4.2. The above problem has a minimizer (a1, . . . , aR) satisfying:
(i) a1 = ∆, and a2 = ∆(∆− 1).
(ii) There is 0 ≤ I ≤ R − 2 such that the sequence a2, . . . , a2+I is increasing and
ai < ∆(∆− 1) for i > 2 + I .
80 Ars Math. Contemp. 21 (2021) #P1.06 / 71–88
(iii) For 3 ≤ i ≤ 2 + I , we have ai + 1 > (ai−1 − 1)(∆− 1).
Suppose that (a1, . . . , aR) is a minimizer that does not satisfy (i), let n ∈ {1, 2} be the
first index such that an < ∆(∆− 1)n−1, and let m ≥ 3 be such that am = max{ai | i ≥
3}. Conditions (C1) and (C2) yield
a1 + a2 ≤ ∆+∆(∆− 1) = ∆2. (4.5)
If ai = 1 for all i ≥ 3, then
R∑
i=1
ai = a1 + a2 +
R∑
i=3
ai ≤ ∆2 +R− 2 < Q− 1
by (4.3), contradicting (C3); this shows that am > 1. The sequence (a′1, . . . , a
′
R) given by
a′i =

ai + 1 for i = n,
ai − 1 for i = m,
ai otherwise.
still satifies (C1)–(C3), and clearly f(a′1, . . . , a
′
R) < f(a1, . . . , aR) since the index n does
not appear in (4.4). It follows that every minimizer has to satisfy (i).
Let us prove that we can obtain a minimizer satisfying both (i) and (ii). Let (a1, . . . , aR)
be a minimizer, and let s be a permutation of {1, . . . , R} so that s(1) = 1, s(2) = 2, and
(a′1, . . . , a
′
R) = (as(1), . . . , as(R))
satisfies (ii); it is obvious that such a permutation always exists. Since s leaves the subset
{3, . . . , R} invariant and the function f is symmetric in those indices, (a′1, . . . , a′R) is also
a minimizer if it satisfies (C1)–(C3).
Let us prove that (a′1, . . . , 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 4.3. For every i ∈ {3, . . . , R} with ai > a2, there is some j ∈ {2, . . . R} such that
j ̸= i and a2 ≤ aj < ai ≤ (∆− 1)aj .
Let l be an integer to be determined later, we are going to define a sequence of indices
m1, . . . ,ml in {2, . . . , R}. Let
m1 = inf{ i ∈ {2, . . . , R} | ai ≥ aj for all 2 ≤ j ≤ R },
and assume am1 > a2, since otherwise the claim is vacuously true. Suppose now that, for
i > 1, we have defined mj for 1 ≤ j < i. If ami−1 = a2, then let l = i− 1, so that mi−1
is the last element in the sequence. If ami−1 > a2, then let
mi = inf{ i ∈ {2, . . . ,mi−1} | ai ≥ aj for all 2 ≤ j ≤ mi−1 }.
The claim is again vacuously true if l = 1, so assume l ≥ 2. It follows easily from the
definition of mi that ami−1 = ami+1 for all 1 ≤ i < l, and thus (C2) yields
ami ≤ (∆− 1)ami−1 = (∆− 1)ami+1 . (4.6)
J. A. Álvarez López et al.: Coarse distinguishability of graphs with symmetric growth 81
Observe that, for every i ∈ {3, . . . , R} such that a2 < ai, there is some j ∈ {1, . . . , l− 1}
such that amj+1 ≤ ai ≤ amj , which combined with (4.6) gives
amj+1 ≤ ai ≤ amj ≤ (∆− 1)amj+1 .
This concludes the proof of Claim 4.3.
We resume the proof of (C2), so let I be the largest non-negative integer so that
a′2, . . . a
′
2+I is increasing. Recall that a
′
2 = a2, and let 3 ≤ i ≤ 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 4.3 there is some
j ∈ {2, . . . , R} such that a2 ≤ aj < as(i) ≤ (∆ − 1)aj . Since aj > a2, we have
2 ≤ s−1(j) ≤ 2 + I by (ii). Also, the sequence a′2, . . . , a′2+I is increasing, so aj ≤ a′i−1
and therefore a′i ≤ (∆−1)a′i−1. Thus Condition (C3) is satisfied because the sum
∑R
i=1 ai
is invariant by permutations, and we have obtained a minimizer (a′1, . . . , a
′
R) that satis-
fies (i) and (ii).
Finally, suppose that (a1, . . . , aR) is a minimizer satisfying (i) and (ii), but not (iii). Let
n be an index such that 3 ≤ n ≤ R − 1 and an + 1 ≤ (an−1 − 1)(∆ − 1), then one can
easily check that the solution (a′1, . . . , a
′
R) given by
a′i =

ai − 1 for i = n− 1,
ai + 1 for i = n,
ai otherwise.
still satifies (C1)–(C3). Furthermore, an+1 ≥ an implies (an+1 + 1)(an − 1) < an+1an,
so f(a′1, . . . , a
′
R) < f(a1, . . . , aR), contradicting the assumption that (a1, . . . , aR) was a
minimizer. This completes the proof of Claim 4.2.
One can easily check that, for every graph X of bounded degree ∆, every x ∈ X , and
every R > 3, the sequence (σx(1), . . . , σx(R)) satisfies (C1)–(C3) for Q = βx(R). Then
Claim 4.2 shows that, for every x ∈ X , there is a sequence (ax,1, . . . , ax,R) satisfying
Claim 4.2(i)–(iii) for Q = βx(R) and such that
R∏
r=3
(σx(r) + 1) ≥
R∏
r=3
(ax,r + 1) (4.7)
Fix such a sequence ax,r for every point x ∈ X . Now (4.5) and Claim 4.2(ii) yield
2+I∑
r=3
ax,r =
R∑
r=1
ax,r −
R∑
r=3+I
ax,r −
2∑
r=1
ax,r
≥ βx(R)− (R− 2− I)∆(∆− 1)−∆2
≥ βx(R)−R∆(∆− 1)− (∆− 1)2. (4.8)
By (C2), we have ax,2+r ≤ ax,2(∆− 1)r for r = 1, . . . , I , so
2+I∑
r=3
ax,r ≤
I∑
r=1
ax,2(∆− 1)r = ax,2(∆− 1)
(∆− 1)I − 1
∆− 2
≤ ax,2∆(∆− 1)I
≤ ∆3(∆− 1)I . (4.9)
82 Ars Math. Contemp. 21 (2021) #P1.06 / 71–88
Since X has symmetric exponential growth, by Lemma 2.5 we have
R∆(∆− 1) + (∆− 1)2 < βx(R)/2
for R large enough and all x ∈ X , so
2+I∑
r=3
ax,r ≥ βx(R)/2 (4.10)
by (4.8), and now (4.9) and (4.10) yield
(∆− 1)I ≥ βx(R)/2∆3. (4.11)
From Claim 4.2(iii) we obtain by induction the following inequality for r = 1, . . . , I .
ax,2+r ≥ ax,2(∆− 1)r − 1− 2
r−1∑
i=1
(∆− 1)i
≥ ax,2(∆− 1)r − 1− 2(∆− 1)
(∆− 1)r−1 − 1
∆− 2
≥ (∆− 1)r(ax,2 −
2
∆− 2
)− 1.
Since ax,2 = ∆(∆− 1) > 2/(∆− 2) + 1, we have
ax,2+r ≥ (∆− 1)r.
Letting C = 1/2∆3, (4.11) yields
R∏
r=3
(ax,r + 1) ≥
2+I∏
r=3
(ax,r + 1) ≥
I∏
r=1
(∆− 1)r = ((∆− 1)I+1)I/2
≥ [Cβx(R)](log∆−1 Cβx(R))/2. (4.12)
Since X has symmetric exponential growth, by Lemma 2.5 there are k, l,m ∈ N such
that kβx(ln) ≥ en for all x ∈ X and n ≥ m. So, if R ≥ lm, then (4.12) yields
R∏
r=3
(ax,r + 1) ≥ (Ck−1e⌊R/l⌋)(⌊R/l⌋+logCk
−1)/2.
Since (Ck−1e⌊R/l⌋)(⌊R/l⌋+logCk
−1)/2 grows faster than ∆8R+7, we can assume that R is
large enough so that
R∏
r=3
(ax,r + 1) > ∆
8R+7
for all x ∈ X . Noting that (∆− 1)2 > 3, equations (2.4) and (4.7) yield
R∏
r=3
(σx(r) + 1) ≥
R∏
r=3
(ax,r + 1)∆[(∆− 1)4R+3]2 ≥ (∆− 1)[βx(4R+ 1)]2.
J. A. Álvarez López et al.: Coarse distinguishability of graphs with symmetric growth 83
Proof of Proposition 3.7. The definitions of A and B in (3.2) yield
R∏
r=3
(σx(r) + 1) =
[∏
r∈A
(σx(r) + 1)
][∏
r∈B
(σx(r) + 1)
]
. (4.13)
We have r − 1 ∈ B for every r ∈ A, so∏
r∈A
(σx(r) + 1) ≤ (∆− 1)
∏
r∈B
(σx(r) + 1) (4.14)
because σx(r) ≤ (∆ − 1)σx(r − 1) by (2.2). The combination of (4.13) and (4.14) then
yields ∏
r∈B
(σx(r) + 1) ≥
√∏R
r=3(σx(r) + 1)
∆− 1
,
and the result follows from Proposition 4.1.
5 Examples
5.1 A connected, locally finite graph with no coarsely distinguishing 2-coloring
For n ∈ Z+, let In = {v0, . . . , vn} be a graph with edges {vm, vm+1} for m = 0, . . . , n−
1, and let X = {um}∞m=1 be a graph with edges {um, um+1} for m ∈ Z+. For every
n ∈ Z+, take 2n + 1 copies of In and denote them by
Iin = { vim | i = 0, . . . , n }, i = 1, . . . , 2n + 1.
For every n and i, glue the graph Iin to X by identifying the points un and v
i
0; denote the
resulting graph by Y (see Figure 2), and let Yn be the full subgraph whose vertex set is the
image of
⋃
i I
i
n by the quotient map.
Figure 2: A graph without coarsely distinguishing 2-colorings
Let ϕ be an arbitrary 2-coloring of Y . Since we have 2n + 1 copies of In glued to un
(n ∈ Z+), by the pigeonhole principle there are at least two indices i(n) ̸= j(n) such that
the restrictions of ϕ to Ii(n)n and I
j(n)
n are equal. So there exists an isomorphism fn of Yn
that preserves ϕ and maps Ii(n)n to I
j(n)
n , and therefore d(f(v
i(n)
n ), v
i(n)
n ) = 2n. Choose
such an isomorphism fn for every n ∈ Z+, and combine them into an isomorphism f of Y
preserving ϕ. Since d(f(vi(n)n ), v
i(n)
n ) = 2n for all n ∈ Z+, the map f is not close to the
identity. Note that the vertex un has degree 4 + 2n, so deg Y = ∞ and hence Y does not
have symmetric growth.
84 Ars Math. Contemp. 21 (2021) #P1.06 / 71–88
5.2 Graphs with infinite motion but finite geometric motion
Perhaps the simplest example of a connected locally finite graph X with m(X) = ∞ and
gm(X) < ∞ 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)) ≤ 1 for all x ∈ X .
x
y
z
Figure 3: Example of a graph X with m(X) = ∞ and gm(X) <∞
We can modify this example to obtain graphs with infinite motion, finite geometric
motion, and faster growth. For example, let T3 be the regular tree of degree 4, and let
ϕ : T3 → {0, 1} be an distinguishing coloring. Substitute each edge in T3 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 ) = {idY } and symmetric exponential growth. Moreover, we can
identify T3 with the subset Y of Y consisting of vertices of degree 4. Gluing one copy of
X to each vertex y ∈ Y by identifying it with x, we obtain a graph with infinite motion,
finite geometric motion, and exponential (but not symmetric) growth.
0 0 0 1 1 1
Figure 4: Substituting each edge in T4 by a graph
5.3 Diestel-Leader graphs
The Diestel-Leader graphs DL(p1, . . . , pn) are defined for n, p1, . . . , pn ≥ 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 Tp and Tq be the regular trees of degree p + 1 and q + 1, respectively. For
i = p, q, choose a root oi ∈ Ti and fix an end ωi of Ti. These choices induce height or
Busemann functions hi : Ti → Z, and then
DL(p, q) := { (x, y) ∈ Tp × Tq | hp(x) + hq(y) = 0 }.
Let us write (x, y) ∈ DL(p, q) as xy for the sake of clarity, and let xEiy denote that x and
y are adjacent in Ti, then the graph structure E in DL(p, q) is defined by
xyEx′y′ if and only if xEpx′ and yEqy′.
J. A. Álvarez López et al.: Coarse distinguishability of graphs with symmetric growth 85
This yields
dDL(p,q)(xy, x
′y′) ≥ max{dTp(x, x′), dTq (y, y′)}
≥ max{| h(x)− h(x′)|, | h(y)− h(y′)|}. (5.1)
For i = p, q, let Aff(Ti) be the subgroup of automorphisms of Ti that fix ωi. For every
f ∈ Aff(Ti), the quantity h(f(x)) − h(x) is independent of x ∈ Ti, and we will denote it
by h(f). Let
Ap,q = { (f, f ′) ∈ Aff(Tp)×Aff(Tq) | hp(f) + hq(f ′) = 0 }.
Lemma 5.1 ([5, Theorem 2.7.], [6, Prop. 3.3]). If p ̸= q, then Aut(DL(p, q)) ∼= Ap,q . For
p = q, the group Aut(DL(p, p)) is generated by Ap,p and the map σ : xy 7→ yx.
Let us prove that DL(p, q) satisfies the hypothesis of Theorem 1.5.
Lemma 5.2. The group Aut(DL(p, q)) has infinite motion, and the stabilizer Sopoq has
infinite geometric motion.
Proof. Let a = (f, f ′) ∈ Ap,q . If a ̸= 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) = ∞.
If moreover a ∈ Sopoq , then f(op) = op, and therefore gm(f) = ∞ when considered
as an automorphism of Tp (it is elementary to check that stabilizers in regular tres have
infinite geometric motion). Now (5.1) yields gm(a) = ∞, proving the result when p ̸= q
by Lemma 5.1.
If p = q, then every automorphism which is not in Ap,q can be written as σa, where
a = (f, f ′) ∈ Ap,p and σ is the map xy 7→ yx. Since f(op) = f ′(op) = op, we have
h(f) = h(f ′) = 0. Let xnyn be a sequence in DL(p, p) with hp(xn) = − hp(yn) = n.
Then
d(xnyn, σa(xnyn)) = d(xnyn, f
′(yn)f(xn)) ≥ | hp(xn)− hp(f ′(yn))|
= | hp(xn)− hp(yn)− hp(f)|
≥ 2n− hp(f),
so gm(a) = m(a) = ∞.
5.4 Graphs with bounded cycle length
A cycle of length n ∈ N in a graph is a path σ of length n with σ(0) = σ(n) and σ(i) ̸=
σ(j) for 0 ≤ i < j < n. A graph X has bounded cycle length if there is L ∈ N such
that every cycle in X has length ≤ 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, Lemma 3.6]). Let X be a connected locally finite graph with infinite
motion, let x ∈ X , and let f ∈ Sx. Then there is a ray γ : N → X such that γ(0) =
f(γ(0)) and im(γ) ∩ im(f ◦ γ) = {γ(0)}.
86 Ars Math. Contemp. 21 (2021) #P1.06 / 71–88
Proof. See the proof of [16, Lemma 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 ∈ X and let f ∈ Sx. By Lemma 5.3, there is a ray γ such that, if we let
γ′ = f(γ), then γ(0) = γ′(0) and im(γ)∩im(γ′) = {γ(0)}. For n ∈ Z+, choose geodesic
paths σn from γ(n) to γ′(n). Let mn be the largest integer such that σn(mn) ∈ im γ, and
let m′n be the least integer such that σn(m
′
n) ∈ im γ′; clearly mn,m′n ≤ d(γ(n), γ′(n)).
The triangle Zn with sides
(γ(0), . . . , γ(i) = σ(mn)),
(σ(mn), σ(mn + 1), . . . , σ(m
′
n)), and
(γ′(j) = σ(m′n), γ
′(j − 1), . . . , γ′(0))
determines a cycle of length ≥ 2n − 2d(γ(n), γ′(n)). Now the assumption that X has
bounded cycle length yields lim d(γ(n), γ′(n)) = d(γ(n), f(γ(n)) = ∞, 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 thatX satisfies the DSC if there is a vertex v ∈ X
such that, for all distinct u,w ∈ X ,
d(v, u) = d(v, w) =⇒ S(u, n) ̸= S(w, n) for infinitely many n. (5.2)
Figure 5: We substitute a vertex x by two copies x1, x2 with the same sphere of radius one
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 ∈ X . Using the substitution shown in Figure 5 on x and y, we can obtain a graph X ′
that has two pairs of vertices xi, and yi (i = 1, 2), instead of x and y, and so that, for any
points u, v ∈ X with u, v ̸= x, y and i ∈ {1, 2},
dX′(xi, u) = dX(x, u), dX′(yi, u) = dX(y, u), dX′(u, v) = dX(u, v), (5.3)
where by abuse of notation we are identifying the points of X \ {x, y} with those of
X ′ \ {x1, x2, y1, y2}. It follows immediately from (5.3) that X ′ shares the same coarse-
geometric properties of X; in particular, X ′ has symmetric growth if and only if X does.
J. A. Álvarez López et al.: Coarse distinguishability of graphs with symmetric growth 87
Let us show that X ′ never satisfies the DSC: Let v ∈ X ′ be arbitrary, then at least one
pair of the new vertices does not contain v, assume v /∈ {x1, x2}. Now (5.3) yields that
d(v, x1) = d(v, x2), but S(x1, n) = S(x2, 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 intro-
duction, 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 de-
note the (unmarked, undirected) Cayley graph of Z2 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 {yi}∞i=0 and
there is an edge yi ∼ yi+1 for every i ≥ 0. It is elementary to check that X satisfies the
DSC. Let Z be the graph obtained by gluing Y to X by identifying y0 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, u). If u,w ∈ X ⊂ Z (we can obviously identify X and Y with subsets of
Z), then
S(u, n) ∩X ̸= S(w, n) ∩ S for infinitely many n
because X satisfies the DSC. If u ∈ X and w = yi ∈ Y for some i > 0, then, for every
n > 0, we have
yi+n ∈ S(w, n) but yi+n /∈ 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.
ORCID iDs
Jesús Antonio Álvarez López https://orcid.org/0000-0001-6056-2847
Ramón Barral Lijó https://orcid.org/0000-0002-5597-1184
Hiraku Nozawa https://orcid.org/0000-0002-3658-5966
References
[1] M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3
(1996), doi:10.37236/1242.
[2] J. A. Álvarez López and R. Barral Lijó, Limit aperiodic and repetitive colorings of graphs,
2018, arXiv:1807.09256.
[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, doi:10.1007/
978-3-319-94132-5.
[4] L. Babai, Asymmetric trees with two prescribed degrees, Acta Mathematica Academiae Scien-
tiarum Hungarica 29 (1977), 193–200.
[5] L. Bartholdi, M. Neuhauser and W. Woess, Horocyclic products of trees, J. Eur. Math. Soc. 10
(2008), 771–816, doi:10.4171/JEMS/130.
[6] D. Bertacchi, Random walks on diestel-leader graphs, Abh. Math. Semin. Univ. Hambg 71
(2001), doi:10.1007/BF02941472.
[7] M. Carter, S. Tornier and G. Willis, On free products of graphs, Australas. J. Combin. 78 (2020),
154–176, https://ajc.maths.uq.edu.au/?page=get_volumes&volume=78.
88 Ars Math. Contemp. 21 (2021) #P1.06 / 71–88
[8] K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13
(2006), doi:10.37236/1042.
[9] J. Cuno, W. Imrich and F. Lehner, Distinguishing graphs with infinite motion and nonlinear
growth, Ars Math. Contemp. 7 (2014), 201–213, doi:10.26493/1855-3974.334.fe4.
[10] R. Diestel and I. Leader, A conjecture concerning a limit of non-Cayley graphs, J. Algebraic
Combin. 14 (2001), 17–25, doi:10.1023/A:1011257718029.
[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 (2011), 1185–1208, doi:
10.1142/9789814324359 0092.
[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 (2012), 221–260, doi:10.4007/annals.
2012.176.1.3.
[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 (2013), 869–910, doi:10.4007/annals.2013.
177.3.2.
[14] S. Hüning, W. Imrich, J. Kloas, H. Schreber and T. W. Tucker, Distinguishing graphs of maxi-
mum valence 3, Electron. J. Combin. 26 (2019), doi:10.37236/7281.
[15] W. Imrich, F. Lehner and S. Smith, Distinguishing density and the distinct spheres condition,
European J. Comb. 89 (2020), doi:10.1016/j.ejc.2020.103139.
[16] F. Lehner, Distinguishing graphs with intermediate growth, Combinatorica 33 (2015), 333–
347, doi:10.1007/s00493-015-3071-5.
[17] F. Lehner and R. G. Möller, Local finiteness, distinguishing numbers, and Tucker’s conjecture,
Electron. J. Combin. 22 (2015), doi:10.37236/4873.
[18] F. Lehner, M. Pilśniak and M. Stawiski, Distinguishing infinite graphs with bounded degrees,
2018, arXiv:1810.03932.
[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 (1998), doi:10.37236/1361.
[21] P. M. Soardi and W. Woess, Amenability, unimodularity, and the spectral radius of random
walks on infinite graphs, Math. Z. 205 (1990), 471–486, doi:10.1007/BF02571256.
[22] T. W. Tucker, Distinguishing maps, Electron. J. Combin. 18 (2011), doi:10.37236/537.
[23] W. Woess, Topological groups and infinite graphs, Discrete Math. 95 (1991), 373–384, doi:
10.1016/0012-365X(91)90348-6.