Aperiodic graphs

Question

The concepts of being non-periodic and aperiodic for tilings have obvious versions for connected graphs with a countable set of vertices and a finite number of edges meeting at each vertex. A graph $G$ of this class is non-periodic when its group of graph isomorphisms is trivial (this is the group of isometries if the graph is considered as a metric space in the usual way). $G$ is aperiodic if its hull consists of non-periodic graphs. Here, the hull of $G$ consists of all graphs of this class that can be expressed as an increasing union of balls with the same center and increasing radius, each of them isometric to some ball in $G$ (using the metric structure). The same definitions have direct versions for graphs with decorations, where a decoration of $G$ is a map assigning a natural number to each vertex of $G$, and the isometries are required to preserve the decorations. Finally, $G$ is said to be of bounded geometry when there is a uniform upper bound on the number of edges that meet at every vertex. Now, the question is the following: If $G$ is of bounded geometry, is there a decoration $\alpha$ of $G$ with finite image such that $(G,\alpha)$ is aperiodic?

Answer 1

[Sorry, can't post this as a comment, not enough rep].

Do you want to answer this claim for every graph $G$? That seems like it could be tricky.

It is easy to consider some simple cases in isolation, though. For $\mathbb{Z}$ one may construct decorations for which the hull will contain all periodic, all non-periodic as well as a mix of periodic and non-periodic. Clearly for a periodic decoration every decorated graph in the hull will also be periodic. For an example of all non-periodic, one could label the vertices using two colours so that the result is a Fibonacci tiling of the line (an example of a Sturmian sequence). All decorated graphs in the hull will correspond to Fibonacci tilings, so will be aperiodic. For a mixture of periodic and non-periodic, just label the central vertex with a different colour to the rest.

Similar examples will work for $\mathbb{Z}^d$ for any $d \in \mathbb{N}$. You could consider more interesting graphs for which the result is aperiodic without any decoration. For example, consider the graph of a Penrose kite and dart tiling and then "split up" the edges depending on their "types" in the tiling (e.g., as a meeting of kites, darts or of a kite and a dart) [edit: one would need to add further decorations if the original tiling had 5-fold symmetry]. This conjures a thought: in principle one may colour edges (as well as vertices) by, instead of assigning decorations, modifying the underlying graph.

Answer 2

This only solves the problem for $\mathbb Z$ but the proof was too long for a comment.

The hull of $\mathbb Z$ has only one graph, $\mathbb Z$, so only the decorations are different for the elements of the hull of a decorated $\mathbb Z$, $G$. The automorphisms of $\mathbb Z$ are just shifts with a possible reflection. Suppose that there is a periodic graph $H$ in the hull for some decoration. If there is a non-zero shift in the automorphsim of $H$, after a while the balls forming $H$ will be larger than the size of the shift, so the periodicity appears in them. Therefore, for some sequence $s$ it is true that for every $t$ there is an interval whose decoration is $t$ times $s$ concatenated, $s^t$. But by recursion it is easy to show that there is a decoration such that every sequence is repeated only a bounded number of times, and no interval longer than four is symmetric.

In fact, now after writing this up, it seems to me that a similar argument should work for any bounded degree graph. Just for every sequence we have to make sure that it won't appear many times under the automorphism of large enough balls.

Update 03.09. Here I describe a construction in more detail for $\mathbb Z$ (the same method works for every graph). We use only two numbers, $0$ and $1$. For every sequence $s$ we make sure that it does not occur more than $t(s)$ times where $t(s)$ are some large numbers. From the above discussion, this is sufficient if no interval longer than four is symmetric. (Imo, this is the main part of the proof and the rest is standard methods.) Using König's lemma, it is enough to give a construction for every finite interval $[1,n]$. Image the possible $2^n$ decorations of this interval as a complete binary tree of depth $n$. When we forbid $00$, the repetition of $0$ twice, then that is equivalent to suitably trimming this tree. After the trimming, we can contract the new degree $2$ vertices into an edge, this way we obtain a new (not complete) binary tree. We can cut down its lower vertices to obtain a new, still quite deep binary tree. Then we repeat the trimming with the next sequence, with a suitable $t(s)$ that does not transform the whole tree after trimming into a path, and so on. Oh, and to make sure that no long intervals are symmetric, first we start trimming the parts that correspond to a repetition.

Answer 3

I couldn't post this as a comment either.

I think one can prove the following weaker property using your ideas: Any countable connected graph of bounded geometry has a finite valued decoration so that any isomorphism of any decorated graph in its hull has some fixed point.

To prove it, let me clarify the following terms for a subset $A$ of a metric space $M$, say (the vertex set of) a graph: $A$ is $C$-separated when $d(x,y)\ge C$ if $x\ne y$ in $A$, and $A$ is a $C$-net when $d(x,A)\le C$ for all $x\in M$. By Zorn's lemma, there exists a $C$-separated $C$-net for all $C>0$. Then we can construct a sequence $M=A_0\supset A_1\supset A_2\supset\cdots$ such that each each $A_n$ is an $2(n+1)$-separated $2(n+1)$-net in $A_{n-1}$, and $\bigcap_nA_n=\emptyset$. Thus $A_n$ is an $(n+1)(n+2)$-net in $M$. Write $A_n=\{x_{n,m}\}$. Let $B_{n,m}$ be the closed ball of center $x_{n,m}$ and radius $n+1$. For each $n\ge1$, the sets $B_{n,m}$ are disjoint. Now take a partition of $\mathbb Z_+$ into sets $I_{n,m}$ such that each $I_{n,m}$ is an interval of $n$ integers $t_{n,m,1}<\dots<t_{n,m,n}$ let $\beta:M\to\{0,1,2,3\}$ be the decoration limit of the decorations $\beta_n$ constructed as follows. Define $\beta_1=3$ on $M\setminus\bigcup_mB_{1,m}$, $\beta_1(x_{1,m})=4$, and $\beta_1(x)=\alpha(t_{1,m,d(x,x_{1,m})})$ if $x\in B_{1,m}\setminus\{x_{1,m}\}$. We follow by induction on $n$. For $n\ge 2$, define $\beta_n=\beta_{n-1}$ on $M\setminus\bigcup_mB_{n,m}$, and $\beta_n(x)=\alpha(t_{n,m,d(x,x_{n,m})})$ if $x\in B_{n,m}\setminus\{x_{n,m}\}$. I think that it is easy to see that, for any decorated graph $(N,\gamma)$ in the hull of $(M,\beta)$, and any isomorphism of $(N,\gamma)$ must fix some point where $\gamma=4$.