16
$\begingroup$

Consider a tiling of the plane using tiles of at least two types (e.g, a Penrose tiling such as that shown at the bottom of this question, which tiles the plane with two types of tiles). List the tile types as $t_1,\ldots,t_k$. Say that an animal using tiles $t_1,\ldots,t_k$ is a connected subset of the plane that can be obtained by gluing a finite number of tiles together along their edges; identify congruent subsets. If there is only one type, this is often called a polyomino; here are some pictures of polyominoes in the square lattice (which has only one type of tile and is not in fact an interesting lattice from the point of view of this question).

(source)

Say that a tiling of the plane using (distinct) tiles $t_1,\ldots,t_k$ is universal if it contains every possible lattice animal using tiles $t_1,\ldots,t_k$. To explain what I mean by "possible", suppose that $k=2$, that $t_1$ is the "thin diamond" from the Penrose tiling and that $t_2$ is the "thick diamond. By gluing together four copies of $t_1$ one can obtain the following "animal".

http://www.math.mcgill.ca/louigi/images/penroseexample.jpg

This animal can't be contained within any tiling (Penrose or otherwise) using $t_1$ and $t_2$. So it makes sense to restrict to animals which, for example, are contained within some tiling of the plane with the given tiles.

My question is: are there $k \geq 2$ for which (aperiodic -- adjective added in edit) universal tilings exist?

Edit: when I first posted the question I omitted the adjective aperiodic above. As pointed out in comments, in this case the answer is obviously yes, which is good to have had pointed out.

We can also restrict the allowed animals. For example, we could restrict to animals which exhibit some form of symmetry.

One could then ask: do aperiodic tilings exist which are universal for animals in a (non-trivial) restricted class? Are there any interesting results along these lines? Is the Penrose tiling itself known to be universal for some interesting class of animals?

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ A 1x1 square and a 2x1 ddomino tile is universal. Also any set containing a 1x1 tile and a set of "supertiles" build from 1x1 tiles is universal. You can do the same on any lattice: pick a fundamental cell and supertiles build by copies from the fundamental cell (for example, hexagons and triangles would work; or a pararlelogram and half of it). I suspect that this is actually the only possibe case, but not sure. I am pretty sure that no aperiodic tile can be universal. $\endgroup$
    – Nick S
    Commented Nov 23, 2010 at 19:43
  • 5
    $\begingroup$ Penrose tiles are universal. Dominos are universal. I'm wondering what is the smallest non-universal polyomino tile? $\endgroup$
    – Peter Shor
    Commented Nov 24, 2010 at 0:04
  • 2
    $\begingroup$ Thanks for these comments. I meant to restrict the tiling to be aperiodic originally; I've modified the question accordingly. $\endgroup$
    – Louigi Addario-Berry
    Commented Nov 24, 2010 at 0:34
  • 2
    $\begingroup$ @Peter Nice question, maybe you should post it. A polyomino such that every patch can be embedded in a rectangle is universal. On that basis I nominate the T tetromino as a candidate. Certain configurations of two tiles can be in a plane tiling but not rectangle (indeed not even a a quarterplane tiling). Of course that does not have to block universality, it only blocks an easy way to prove universality. $\endgroup$
    – Aaron Meyerowitz
    Commented Nov 25, 2010 at 3:29
  • 6
    $\begingroup$ It seems that the link to the picture in the post is not working now math.mcgill.ca/louigi/images/penroseexample.jpg Is this the correct new link: problab.ca/louigi/images/penroseexample.jpg ? $\endgroup$
    – Martin Sleziak
    Commented Nov 17, 2017 at 7:01

2 Answers 2

Reset to default
9
$\begingroup$

I thought that EVERY plane tiling by the two Penrose tiles is universal (later I checked, that is indeed the case as Peter explains nicely below). It is cheap but you could take any (set of) possible animal(s) and call them new tiles. I think that Penrose started with a set of 6 tiles, probably with the same property (and probably derivable in the way I mentioned from the two tile set). You could also split one or both Penrose tiles into weird pieces which only fit together to recreate that piece.

If I recall correctly, it is an open question if there is a single tile which only tiles aperiodically. SO it is premature to ask if there is one which has a universal tiling (not that you asked that).

In the periodic case (from when that was part of the question) I can certainly specify two (or even any k) gawky tiles which only tile in one way so that is automatically universal. It is easier to think of colored tiles. (maybe squares constrained to fit 4 at each corner) it is easy to see how to make a universal tiling. There are ways to replace these with huge squarish polyomonoes with lock and key bumps.

Improve this answer
$\endgroup$
7
  • 5
    $\begingroup$ Every finite subregion of a Penrose tiling is contained in every other Penrose tiling, but you can construct lattice animals from Penrose tiles (with the correct edge matching rules) which cannot be completed to Penrose tilings of the entire plane. $\endgroup$
    – Peter Shor
    Commented Nov 23, 2010 at 22:29
  • 3
    $\begingroup$ True. The OP asked if there is some Penrose tiling which contains every possible animal (as he defined it). In fact EVERY Penrose tiling contains every possible animal. However no Penrose tiling contains any impossible animal. But that is implicit in the definition of possible. $\endgroup$
    – Aaron Meyerowitz
    Commented Nov 24, 2010 at 1:41
  • $\begingroup$ I see. The point is that the matching rules in the Penrose tiling precisely imply that the set of possible animals is equal to the set of animals that actually appear in the Penrose tiling. I was missing this point. Thanks! $\endgroup$
    – Louigi Addario-Berry
    Commented Nov 24, 2010 at 2:46
  • 2
    $\begingroup$ @Aaron: You say "it is an open question if there is a single tile which only tiles aperiodically". I'd like to point out that that question got almost solved in the paper "Forcing nonperiodicity with a single tile", by J. Socolar, and J. Taylor. Arxiv: xxx.lanl.gov/abs/1009.1419 $\endgroup$
    – André Henriques
    Commented Nov 24, 2010 at 9:32
  • 2
    $\begingroup$ @Aaron: There are exactly two Penrose tilings with 5-fold symmetry: Figures 7 and 8 in (math.brown.edu/~res/MFS/handout7.pdf). $\endgroup$
    – Peter Shor
    Commented Nov 25, 2010 at 20:38
5
$\begingroup$

A very nice reference on this family of questions is Grunbaum and Shephard's book Tilings and Patterns (now out in paperback). It has starred problems which are hard, and double-starred problems which are research projects. It is in this book that we find the problem of whether there is a tile which only tiles aperiodically. (There is such a beast for the 3-dimensional analog, but it's a bit of a cheat.) I contacted Grunbaum about this a few years ago, and he said the problem was still open.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .