5
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ I don't understand the question. Aperiodic and non-periodic are two different things? What is "this class"? Countable, finite degree graphs? The hull is a family of finite or infinite graphs? $\endgroup$
    – domotorp
    Mar 6, 2015 at 15:05
  • $\begingroup$ The terms non-periodic and aperiodic are used with different meanings here. The considered class consists of connected countable graphs with finite degree at each vertex, but, in the question, one takes a graph with uniformly bounded degree for all vertices. If the graph is infinite, its hull also consists of infinite graphs. If a graph is finite, its hull only has that graph. $\endgroup$ Mar 6, 2015 at 15:58
  • $\begingroup$ Could you maybe provide a link for these notions or give an example for the hull of an infinite graph? $\endgroup$
    – domotorp
    Mar 6, 2015 at 21:05
  • 1
    $\begingroup$ Consider for instance the Cayley graph $G$ of the $\mathbb Z$, with the decoration $\alpha$ of the form: $\cdots-1-0-0-0-1-0-0-1-0-1-0-0-1-0-0-0-1-\cdots$. Then the decorated graph $\cdots-0-0-0-\cdots$ is in the hull of $(G,\alpha)$ because its a union of decorated balls with the same center and increasing radius that are isometric to decorated balls in $(G,\alpha)$. $\endgroup$ Mar 6, 2015 at 22:17
  • $\begingroup$ I see, so a graph G' is in the hull of G, if when you "look around" in G' for a finite number of steps, you might as well be in G. $\endgroup$
    – domotorp
    Mar 6, 2015 at 23:11

3 Answers 3

4
$\begingroup$

[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.

$\endgroup$
4
  • $\begingroup$ So the Fibonacci tiling gives an affirmative answer to the question for $\mathbb Z$, and there are similar constructions solving the problem for $\mathbb Z^d$. I'd like to have an affirmative answer for any graph of bounded geometry without modifying the graph, only equipping it with a decoration having a finite number of values. Could some version of the Fibonacci tiling on the line work for any graph of bounded geometry? $\endgroup$ Mar 8, 2015 at 22:36
  • $\begingroup$ When I first saw this question, my initial idea was to try and decorate all infinite paths with aperiodic sequences (like the fibonacci as mentioned above), but the difficulty seems to be in how to guarantee that one doesn't leave arbitrarily large gaps in the graph. If there was some sufficiently nice class of graphs that all graphs of your type can be identified as subgraphs of, that might make the problem a bit more manageable. $\endgroup$
    – Dan Rust
    Mar 8, 2015 at 22:51
  • $\begingroup$ @Daniel: Same here, this was my first idea too. $\endgroup$
    – domotorp
    Mar 9, 2015 at 8:30
  • $\begingroup$ Yes, this idea seems pretty natural. It will work in examples such as Cayley graphs of free groups, by simply decorating each infinite path as a Fibonacci tiling. But the issue is when things aren't free, so that one needs to check that the decorations of paths are consistent on overlaps! $\endgroup$ Mar 9, 2015 at 23:11
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I don't quite understand your argument. First of all, is your answer YES or NO for the case of $\mathbb Z$? $\endgroup$ Mar 7, 2015 at 22:31
  • $\begingroup$ YES. Let me know what part is unclear. $\endgroup$
    – domotorp
    Mar 7, 2015 at 22:45
  • $\begingroup$ Could you explain the recursive construction of an example of a decoration on $\mathbb Z$ with finite values such that every sequence is repeated only a bounded number of times, and no interval longer than four is symmetric? $\endgroup$ Mar 8, 2015 at 22:14
  • $\begingroup$ In your update, how is the tree structure in the set of possible decorations for $[0,n]$? $\endgroup$ Mar 9, 2015 at 9:13
  • $\begingroup$ In $\mathbb Z$, the aperiodicity of a decoration $\alpha$ means that there is a sequence of naturals $k_n\uparrow\infty$ such that, for each interval $I\subset\mathbb Z$ of length $n$, the ``copies'' of $(I,\alpha|_I)$ in $(\mathbb Z,\alpha)$ are at a distance $\ge k_n$ from each other. Is this what you look for in your construction? $\endgroup$ Mar 9, 2015 at 10:07
0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Where can I find a proof of the aperiodicity of the Fibonacci tiling of the line? $\endgroup$ Mar 10, 2015 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.