Coarse distinguishability of graphs with symmetric growth

ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P1.06 https://doi.org/10.26493/1855-3974.2354.616 (Also available at http://amc-journal.eu) Coarse distinguishability of graphs with symmetric growth* Jes´ us Antonio ´ Alvarez L´ opez Departamento e Instituto de Matem´ aticas, Facultade de Matem´ aticas, Universidade de Santiago de Compostela, 15782 Santiago de Compostela, Spain Ram´ on Barral Lij´ o† 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 Xbe a connected, locally finite graph with symmetric growth. We prove that there is a vertex coloring φ:X→ {0,1}and some R∈Nsuch 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 Sxsatisfies the following condition: for every nonidentity automorphism f∈Sx, there is a sequence xnsuch 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 Ritsumeikan University and grants FEDER/Ministerio de Ciencia, Innovaci´ on y Universidades/AEI/MTM201789686-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.alv[email protected] (Jes´ us Antonio ´ Alvarez L´ opez), [email protected] (Ram´ on Barral Lij´ o), hnozaw[email protected] (Hiraku Nozawa) cb This work is licensed under https://creativecommons.org/licenses/by/4.0/ 2 Ars Math. Contemp. 21 (2021) #P1.06 1 Introduction A (not necessarily proper) vertex coloring φof a graph is distinguishing if the only automorphism that preserves φis the identity. This notion was first introduced in [4] under the name asymmetric coloring, where it was proved that 2colors suffice to produce a distinguishing coloring of a regular tree. Later, Albertson and Collins [1] defined the distinguishing number D(X)of a graph Xas 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,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 fis the cardinality of the set of points that are not fixed by f. For a graph X and a subset A⊂Aut(X), the motion of Ais m(A) = inf{m(f)|f∈A, f 6= id}, and the motion of Xis m(X) = m(Aut(X)). A probabilistic argument yields the following result for finite graphs. Lemma 1.1 (Motion Lemma, [20]).If Xis a finite graph and 2m(X)≥ | Aut(X)|2, then D(X)≤2. We always have |Aut(X)|2≤2ℵ0when Xis countable, which motivates the following generalization. Conjecture 1.2 (Infinite motion conjecture, [22]).If Xis 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,1and later, together with M. Pil´ sniak 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 Sxsatisfying that, for every automorphism f∈Sx\ {id}, there is a sequence xnsuch that d(xn, f(xn)) → ∞; we can regard this condition as a geometric refinement of having infinite motion. Let Xand Ybe connected graphs, endowed with their canonical N-valued2metric. In the context of coarse geometry (see [19] for a nice exposition on the subject), two functions f, g :X→Yare R-close (R≥0) if d(f(x), g(x)) ≤Rfor all x∈X, and we say that fand gare 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 closeness class. We can adapt the notion of distinguishing coloring to this setting as follows: Definition 1.3. A coloring φ:X→Nis 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. ´ Alvarez L´ opez et al.: Coarse distinguishability of graphs with symmetric growth 3 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, Corollary 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.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 Xbe a connected, locally finite graph of symmetric growth. Then there are R∈Nand φ: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 Rfor all f∈Aut(X, φ); 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 Xcontaining a vertex x∈Xsuch 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 Xbe a connected graph and let f∈Aut(X). The geometric motion of fis then gm(f) = sup{d(x, f(x)) |x∈X}; for a subset A⊂Aut(X), the geometric motion of Ais gm(A) = sup{gm(f)|f∈ A, f 6= id}. The definition of the “closeness” relation for functions yields that the restriction ι: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 Xbe a connected, locally finite graph with symmetric growth. If m(X) = ∞and there exists x∈Xsuch 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 p6=qanswer 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 2colors 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 4 Ars Math. Contemp. 21 (2021) #P1.06 (DSC) [15, Theorem 4]. A connected graph Xsatisfies 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)6=S(w, n)for infinitely many n. (1.1) Since both symmetric growth and the DSC prove the existence of distinguishing colorings by 2colors for the same family of graphs, it is natural to ask if there is any relation between these two notions; in Section 5we 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 > 0and a subset Y⊂Xsuch that d(x, Y )≤Rfor all x∈X. Suppose that there is a partial coloring ψby two colors such that, if φ:X→ {0,1}is an extension of ψ and fis an automorphism of Xpreserving φ, then f(Y) = Y. Thus we can regard every extension φof ψas a coloring ¯ φ:Y→Nby more than two colors. The hypothesis of symmetric growth ensures that, for Rlarge enough, we have sufficiently many local extensions of ψaround every point y∈Yso 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 preliminaries to be used in the proof of the main theorems, which comprises Sections 3and 4. Finally, Section 5contains 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 Xis deg X= sup{deg x|x∈X}. A graph Xis locally finite if deg x < ∞for all x∈X. A path γin Xof length l∈Nis a finite sequence x0, x1, . . . , xl of vertices such that xi−1EXxifor all i= 1, . . . , l; when the sequence of vertices is infinite, we call γaray. 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 xand y; a length-minimizing path is termed a geodesic path. Apartial coloring of a graph Xis a map ψ:Y→N, where Y⊂X; if Y=X, we simply call ψacoloring. We use the term (partial) 2-coloring when ψtakes values in {0,1}. For every graph Xand coloring φ:X→N, let Aut(X, φ)denote the group of automorphisms fof Xsatisfying φ=φ◦f. A coloring φ:X→Nis 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 xand radius r, respectively. We may write DX(x, r)for D(x, r)when the ambient space Xis not clear from context. A subset Y J. A. ´ Alvarez L´ opez et al.: Coarse distinguishability of graphs with symmetric growth 5 of Xis R-separated (R > 0) if d(y, y0)≥Rfor all y, y0∈Ywith y6=y0; it is R-coarsely dense if, for every x∈X, there is some y∈Ywith d(x, y)≤R. Lemma 2.1 (E.g. [2, Corollary 2.2.]).Let Xbe a graph and let R > 0. For every x∈X, there is a (2R+ 1)-separated, 2R-coarsely dense subset Y⊂Xcontaining 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 Xbe a countable graph, and let Anbe 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 2Xis sequentially compact with the topology of pointwise convergence3, so there is a convergent subsequence Sni→S. It is now elementary to check that Sis a (2R+ 1)-separated, 2R-coarsely dense subset of X. Let βx:N→Nand σx:N→Nbe the functions defined by βx(r) = |D(x, r)|, σx(r) = |S(x, r)|. Given two non-decreasing functions f, g:N→R+,fis dominated by gif 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 βxdoes 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 graph Xhas symmetric growth if there are k, l, m ∈ Nsuch that βx(r)≤kβy(lr)for all r≥mand x, y ∈X. Lemma 2.4. If Xhas symmetric growth, then deg X < ∞. Proof. Let x∈X, then we have deg y < βy(1) ≤kβx(lm)<∞for every y∈X. Let Xbe a graph with ∆ := deg X < ∞, then the following holds for all x∈Xand 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 X s=0 (∆ −1)s= 1 + ∆((∆ −1)r−1) ∆−2 ≤1 + 3(∆ −1)r−1 = 3(∆ −1)r.(2.4) We say that Xhas exponential growth if lim inf log βx(r) r>0for 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. 6 Ars Math. Contemp. 21 (2021) #P1.06 Lemma 2.5. Let Xbe a graph with symmetric exponential growth. Then there are k, l, m ∈ Nsuch that er≤kβx(lr)for all x∈Xand r≥m. Lemma 2.6. If Xhas symmetric subexponential growth, then, for every a, b > 0, there is some m∈Nsuch that βx(r)≤aebr for all x∈Xand r≥m. 3 Construction of the coloring Let Rbe a large enough odd number, to be determined later. Let Ybe a (2R+1)-separated, 2R-coarsely dense subset of X; we define a graph structure EYon Yas follows: yEYy0if and only if 0< d(y, y0)≤4R+ 1.(3.1) Lemma 3.1. The graph (Y, EY)is connected with degYy≤ |DX(y, 4R+ 1)| − 1for all y∈Y. Proof. The inequality follows trivially from (3.1), so let us prove that Yis connected. Let y, y0∈Y, and let (y, x1, . . . , xn−1, y0)be a path in X. Since Yis 2R-coarsely dense, for every i= 1, . . . , n there is some yi∈Ywith dX(xi, yi)≤2R. The triangle inequality and (3.1) then yield that (y, y1, . . . , yn−1, y0)is a path on (Y, EY). Recall that Ris 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 Yis (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 1for an illustration): ψ(x) =          0, x ∈Sr=0,1S(Y, r), 1, x ∈S(Y, 2), 1, x ∈Sr∈AS(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∈Ysuch that d(¯y, f(y)) ≤1and d(z, ¯y) = d(z, f(y)) for all z∈X\ {¯y, f(y)}. J. A. ´ Alvarez L´ opez et al.: Coarse distinguishability of graphs with symmetric growth 7 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 Y0={z∈X|φ(z0)=0for all z0∈D(z, 1) }, then (3.3) yields Y0⊂D(Y, 1), and clearly f(Y0) = Y0for all f∈Aut(X, φ). For y∈Y, let ¯ybe the unique vertex in Ywhich is adjacent to f(y). We have φ(z) = 0 for every vertex z∈D(f(y),1) and D(f(y),1) ⊂D(¯y, 2), so D(f(y),1) ⊂D(¯y, 1) by (3.3). Since D(¯y, 1) ⊂D(f(y),2), we also get D(¯y, 1) ⊂D(f(y),1), and the result follows. Corollary 3.3. If Xhas infinite motion, then f(Y) = Y. Proof. Let f∈Aut(X, φ)and suppose f(y)6= ¯y. By the previous lemma we have D(f(y),1) = D(¯y, 1), so there is a non-trivial automorphism exchanging f(y)and ¯yand leaving all other vertices in Xfixed. This contradicts the assumption that Xhas infinite motion. Remark 3.4. Note that there might be automorphisms f∈Aut(X, φ)with f(Y)6=Y when m(X)<∞. The graph in Figure 1provides such an example: the map fthat interchanges y1and zand leaves the rest of vertices fixed is an automorphism preserving ψ, but f(Y)6=Y. Since dom ψ=X\Sr∈BS(Y, r), an extension of ψto Xis the same thing as a coloring of Sr∈BS(Y, r); for such an extension φ, let ¯ φdenote the induced coloring Y→ QBNdefined by ¯ φ(y) = (¯ φr(y))r∈B,where ¯ φr(y) = |S(y, r)∩φ−1(1)|.(3.4) Lemma 3.5. If ξ:= (ξr)r∈B:Y→QBNis such that ξr(y)≤σy(r)for every y∈Y, then there is at least one extension φsatisfying ¯ φ=ξ. 8 Ars Math. Contemp. 21 (2021) #P1.06 Proof. Since Yis (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 1and 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 ¯ fbe defined by the formula ¯ f(y) = ¯y, where ¯y∈Ydenotes 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, y0) = d(f(y), f(y0)) = d(¯ f(y),¯ f(y0)) for every y, y0∈Y,y6=y0. This equation and (3.1) yield that ¯ fis an automorphism of Y; moreover, f(S(y, r)) = S(f(y), r) = S(¯ f(y), r) for r≥1by Lemma 3.2, so ¯ fpreserves ξby (3.4). Proposition 3.7. If Xhas symmetric growth, then we can choose Rlarge enough so that Qr∈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 Xhas symmetric growth and that Rhas been chosen satisfying the statement of Proposition 3.7. Proposition 3.8. There is a distinguishing coloring ξ:= (ξr)r∈B:Y→QBNsuch that ξr(y)≤σy(r)+1. Proof. Choose a spanning tree Tfor (Y, EY)and a root y0∈Y. In order to define ξ, first let ξ(y0) = (0,...,0). Every y∈Ywith y6=y0has at most |DX(y, 4R+ 1)| − 1siblings in Tby Lemma 3.1. Using Proposition 3.7, we can define ξso that ξ(y)6= (0,...,0) for all y6=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→Nis distinguishing. By Lemma 3.6, every f∈Aut(X, φ)satisfies d(f(y), y)≤1for all y∈Y. Since Yis 2R-coarsely dense, the triangle inequality yields d(x, f(x)) ≤4R+ 1 for all x∈X. Proof of Theorem 1.5.Let Xhave infinite motion and pick x∈Xso that Sxhas infinite geometric motion; Lemma 2.1 ensures that we can choose Yso that x∈Y. Using Lemma 3.5 and Proposition 3.8, we construct a coloring φ:X→ {0,1}extending ψand such that ¯ φis distinguishing. Since Xhas infinite motion, Corollary 3.3 yields f(Y) = Yfor every f∈Aut(X, ψ). Moreover, Lemma 3.6 and the fact that ¯ φis distinguishing show that f|Y= idY, so Aut(X, φ)⊂Sx. Since gm(Sx) = ∞by hypothesis, gm(Aut(X, φ)) = ∞. But Yis a 2R-coarsely dense subset and is fixed pointwise by every automorphism f, so the triangle inequality yields d(x, f(x)) ≤4Rfor all x∈X, a contradiction. J. A. ´ Alvarez L´ opez et al.: Coarse distinguishability of graphs with symmetric growth 9 4 Growth estimates In this section we assume that Xis a graph with symmetric growth. We will derive Proposition 3.7 from the following result: Proposition 4.1. For Rlarge enough, we have QR 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 Xis a graph of symmetric subexponential growth. Indeed, since Xis infinite, we have σx(r)≥1for all x∈X, r≥0, so R Y r=3 (σx(r) + 1) ≥2R−2=1 4eRlog 2.(4.1) Using Lemma 2.6, we have that, for Rlarge enough, βx(4R+ 1) ≤1 8(∆ −1)e[(4R+1) log 2]/10 ≤1 8(∆ −1)e(Rlog 2)/2(4.2) for every x∈X. Combining now (4.1) and (4.2), we get (∆ −1)[βx(4R+ 1)]2≤1 8eRlog 2 ≤ R Y r=3 (σx(r) + 1), as desired. So, for the purposes of this proof, we will assume from now on that Xis a graph with symmetric exponential growth. In order to obtain lower bounds for the function QR r=3(σx(r) + 1), let us consider the following optimization problem: given ∆, Q, R ∈Nwith ∆>2, R > 3, Q > ∆2+R−1,(4.3) minimize the function f(a1, . . . , aR) = R Y i=3 (ai+ 1) (4.4) for a= (a1, . . . , aR)∈(Z+)Rsatisfying a1≤∆,(C1) ai≤ai−1(∆ −1),(C2) R X 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−2such that the sequence a2, . . . , a2+Iis increasing and ai<∆(∆ −1) for i > 2 + I. 16 Ars Math. Contemp. 21 (2021) #P1.06 Proof. See the proof of [16, Lemma 3.6]. Proposition 5.4. If Xhas infinite motion and bounded cycle length, then every vertex stabilizer has infinite geometric motion. Proof. Let x∈Xand let f∈Sx. By Lemma 5.3, there is a ray γsuch that, if we let γ0=f(γ), then γ(0) = γ0(0) and im(γ)∩im(γ0) = {γ(0)}. For n∈Z+, choose geodesic paths σnfrom γ(n)to γ0(n). Let mnbe the largest integer such that σn(mn)∈im γ, and let m0 nbe the least integer such that σn(m0 n)∈im γ0; clearly mn, m0 n≤d(γ(n), γ0(n)). The triangle Znwith sides (γ(0), . . . , γ(i) = σ(mn)), (σ(mn), σ(mn+ 1), . . . , σ(m0 n)),and (γ0(j) = σ(m0 n), γ0(j−1), . . . , γ0(0)) determines a cycle of length ≥2n−2d(γ(n), γ0(n)). Now the assumption that Xhas bounded cycle length yields lim d(γ(n), γ0(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 that Xsatisfies 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)6=S(w, n)for infinitely many n. (5.2) Figure 5: We substitute a vertex xby two copies x1, x2with the same sphere of radius one We will begin by showing how to modify a graph Xto obtain a similar graph X0that does not satisfy the DSC. Let Xbe any connected graph, and take two different points x, y ∈X. Using the substitution shown in Figure 5on xand y, we can obtain a graph X0 that has two pairs of vertices xi, and yi(i= 1,2), instead of xand y, and so that, for any points u, v ∈Xwith u, v 6=x, y and i∈ {1,2}, dX0(xi, u) = dX(x, u), dX0(yi, u) = dX(y, u), dX0(u, v) = dX(u, v),(5.3) where by abuse of notation we are identifying the points of X\ {x, y}with those of X0\ {x1, x2, y1, y2}. It follows immediately from (5.3) that X0shares the same coarsegeometric properties of X; in particular, X0has symmetric growth if and only if Xdoes. J. A. ´ Alvarez L´ opez et al.: Coarse distinguishability of graphs with symmetric growth 17 Let us show that X0never satisfies the DSC: Let v∈X0be 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 X0does not satisfy the DSC. This procedure can be used to obtain examples of graphs of symmetric and nonsymmetric 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 Xdenote the (unmarked, undirected) Cayley graph of Z2with respect to the generating set {(0,1),(1,0)}, and let Ybe a semi-infinite ray; that is, the vertex set of Yis {yi}∞ i=0 and there is an edge yi∼yi+1 for every i≥0. It is elementary to check that Xsatisfies the DSC. Let Zbe the graph obtained by gluing Yto Xby identifying y0and (0,0), and let us see that Zstill satisfies the DSC: Let v= (0,0), and let u, w be distinct vertices in Zwith d(v, u) = d(v, u). If u, w ∈X⊂Z(we can obviously identify Xand Ywith subsets of Z), then S(u, n)∩X6=S(w, n)∩Sfor infinitely many n because Xsatisfies the DSC. If u∈Xand w=yi∈Yfor 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 Zalso satisfies the DSC. Moreover, since Yhas linear growth and Xhas quadratic growth, it is easy to check that Zhas non-symmetric growth. ORCID iDs Jes´ us Antonio ´ Alvarez L´ opez https://orcid.org/0000-0001-6056-2847 Ram´ on Barral Lij´ ohttps://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. ´ Alvarez L´ opez and R. Barral Lij´ o, Limit aperiodic and repetitive colorings of graphs, 2018, arXiv:1807.09256. [3] J. A. ´ Alvarez L´ opez 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 Scientiarum 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. 18 Ars Math. Contemp. 21 (2021) #P1.06 [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¨ uning, W. Imrich, J. Kloas, H. Schreber and T. W. Tucker, Distinguishing graphs of maximum 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¨ oller, Local finiteness, distinguishing numbers, and Tucker’s conjecture, Electron. J. Combin. 22 (2015), doi:10.37236/4873. [18] F. Lehner, M. Pil´ sniak 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.