ConwayLife.com

I wrote about this at length in the Thread for non-CA academic questions but I'm trying again in the hope that someone can help. I am sure all of my observations on these tilings have been made before, but I don't know where I would begin to look up the relevant research. Here is another observation about the two-coloring, as illustrated by this picture. To get the same coloring as wavy rhombus tiles, you can require that tiles switch colors when going in a straight line and keep the same color going around a bend. This picture uses red and blue for the two colors. If you shade the tiles according to orientation (0°, 120°, 240°) then you get the kind of rough 3D effect used in some Roman mosaics and the old video game Q*bert.

This isn't just coincidence. The rhombus tiling is an isometric projection of stacks of cubes. These need to be monotonically non-decreasing in height (i.e. no stack is higher than one behind). And what about the red-blue colors? For those to work out, you just need the rule that no two cubes can have the same color if they are adjacent along a face. So this tiling is like a surface carved out of a 3D checkerboard.

In that sense, we have a way to derive these colored 2D tilings that may not be periodic from a regular two-colored cube lattice (as noted in the earlier post, the colorings can be enforced by a single two-sided piece with an "s" and a "z" orientation).

Maybe this comes up in crystallography? Is strikes me as an elegant connection between several things (tilings, isometric projection, bipartite matching among others). I am not sure if it is "useful" or leads to anything else.

And I am now reminded of Michelangelo's famous statement:

The sculpture is already complete within the marble block, before I start my work. It is already there, I just have to chisel away the superfluous material.

Each bichromatic rhombic tiling is complete within the cubic checkerboard lattice. You just have to remove the superfluous material!

Chiseling away the superfluous material in Q*bert space. I think any rhombus tiling can be constructed this way and will be colored so that colors alternate on straight lines and stay the same around bends. I don't have a proof. (Must be known though, right?)

pcallahan wrote:I don't know where I would begin to look up the relevant research.

The woodcuts by M.C. Escher

A Picture Language created by Peter Henderson

Lisp: A Language for Stratified Design
By Harold Abelson and Gerald Jay Sussman
Byte February 1988

Structure and Interpretation of Computer Programs
Harold Abelson and Gerald Jay Sussman
Example 2.2.4 A Picture Language
Available on line at:
https://web.mit.edu/alexmv/6.037/sicp.pdf

A Java implementation:
http://bprentice.webenet.net/Patterns/Standalone.zip

Brian Prentice

bprentice wrote: The woodcuts by M.C. Escher
...

These seem to be a bit too general in nature, and evade my question, which is about the underlying mathematics, not how to represent the pictures. (Obviously I'm familiar with Escher, but my pictures are not paradoxical.)

E.g., can someone recommend a paper that specifically concerns the mapping between isometric projections of surfaces in a cubic lattice and tilings with rhombuses or a class of such isomorphisms. Some of this is obvious in retrospect, but it took me weeks of work to get there. (I have Grünbaum and Shephard's Tilings and Patterns, and if this has a relevant result, I may just not have the wherewithal to understand it.)

So in short, what kind of specialist would find this obvious or at least find the analysis very familiar? (Not a computer scientist, or not me anyway.)

Or another way to put it: I've rediscovered something a little bit interesting. What's it called? It is not called Escher woodcuts or Lisp, and probably not a picture language either. It is something about projections of monotonically nondecreasing surfaces in a cubic lattice and the connection to tilings and bipartite matchings.

Parts of this are readily explained in terms of geometry, but it took a while to get there. First off, the "Q*bert" isometric projection is onto the plane x+y+z=0, so the axes can be placed as follows. The 2 colors come from this observation (italics because this is really the key to explaining most of what's going on):

When you follow an adjacent rhombus in the same direction, you increase or decrease x, y, or z, thus increasing or decreasing x+y+z accordingly.

When you follow a rhombus around a bend, you increase (decrease) one axis and (decrease) increase the other axis, leaving x+y+z unchanged.

The colors (red and blue in the Q*bert picture) are based on whether x+y+z is odd or even, assuming cubes are placed at integer coordinates. Hence, they alternate on straight paths, but stay the same around bends.

Here is the part that is at least fairly interesting. We have 3 distinct discrete systems that are equivalent:

(1) A bipartite graph in a triangular grid in which an edge between two adjacent triangles may be included in a matching.
(2) A rhombus tiling in which each rhombus covers two adjacent grid triangles and rhombuses are colored the same as adjacent ones with a different orientation, or the opposite color to an adjacent one with the same orientation.
(3) A surface of exposed square facets in a cube lattice, projected as rhombuses onto the plane x+y+z=0, and colored according to whether their x+y+z is odd or even (parity).

The connection between (1) and (2) is a classic result used, among other things, for counting packings of rectangular grids by dominoes. The connection between 2 and 3 is a bit more subtle, though I am sure it is an old, standard result (where?).

So if you remove or add a cube to the surface (3), the operation on the isometric projection is effectively a local retiling of 3 rhombuses (2) and this is also explicable as switching matching edges with unmatched edges in an alternating path in a bipartite graph (1).

I find this surprising. Anyone else? And someone who does not find it surprising may be able to help.

Paul,

These arrangements of cubes are called 'plane partitions', and their correspondence with rhombus tilings of hexagonal regions is well understood: http://nyjm.albany.edu/j/1998/4-10.pdf

calcyman wrote:Paul,

These arrangements of cubes are called 'plane partitions', and their correspondence with rhombus tilings of hexagonal regions is well understood: http://nyjm.albany.edu/j/1998/4-10.pdf

Thanks! I will have to take a look at that. I was certain I had not found anything new in terms of results, but there is some potential for puzzles here. I had always thought of Q*bert graphics as a cheap trick when there is actually basis for it.

I also found Tiling polygons with parallelograms which seemed relevant, but I will look at your reference first.

(Funny, I met James Propp years back if I'm not confusing him with someone else, and have a mutual acquaintance with no connection to computer science or mathematics.)

Perfect! This is what I was saying about the bichromatic coloring. (from paper by Henry Cohn, Michael Larsen, and James Propp)

Colors are based on odd-even parity of the height function. I was playing around with the double-sided wavy rhombus for weeks before seeing that. (I still like the wavy rhombus, though some of the "magic" is gone now.)

And yes calcyman nailed my request: "E.g., can someone recommend a paper that specifically concerns the mapping between isometric projections of surfaces in a cubic lattice and tilings with rhombuses or a class of such isomorphisms." That is what I wanted. I was never very good at doing a literature search. I did try, but I am not sure I would have found this.

I don't think I mentioned in either thread, but the rhombus packing actually came up as a digression when looking at matching triominoes. Specifically, take the following two triominoes, crudely shown in text graphics. These represent equilateral triangle tiles with vertices marked 0 or 1, where neither has the same marking for all vertices.
Match these tiles according to triomino rules. so that all 6 triangles packed around each vertex have the same number, 0 or 1. The vertices are the dual of a hex grid, so another way to look at this is that for any three hexes incident to the same corner in the dual grid, two must be 0 or two must be 1, but they cannot all be 0 or 1.

Draw an edge between hexes of opposite color, and you have your rhombuses again. Or, less abstractly, this figure illustrates the isomorphism between triominos (with colors instead of numbers) and the wavy rhombus tiles (which are themselves planar partitions labeled by the parity of the height). The triomino system puzzled me for a long time. It seemed vaguely like something that could be reduced to bipartite matching, but I went through a lot of false starts before getting to the above. There are a number of effective methods of making random rhombus packings/triomino matchings that I implemented without really using augmenting paths as in a matching. It is not a hard problem to solve when unconstrained.

In fact, the 0-1 markings of the triominos are simply the parity of the height of cube vertices, as shown in figure 3 of Cohn, Larsen, and Propp, which I posted above.

Since the black-white tile colors above correspond to the plane partition height mod 2, this can be generalized by using more wavy tiles with other matching contours. If there is an even number of colors 2k, you can always reuse a tile by flipping it, so only k unique tile shapes are needed (up to rotation and flipping). E.g. to get plane partition height mod 4, you need two asymmetrical contours that span the edge of a rhombus. The first tile uses a contours a and b. The second tile uses the contour b and the mirror image of a (flipped a). Then you can chain tile 1 (a, b), tile 2 (b, flipped a), flipped tile 1 (flipped a, flipped b), flipped tile 2 (flipped b, a), and back to tile 1.

To generalize it to 6, 8, 10 colors, etc. the last tile in the sequence includes the mirror image of the first contour (so far not matched to any previous tile). It's analogous to putting a twist in a loop (like a mobius strip) and I imagine mathematicians have a name for it.

E.g.: Close up of the tiles with thinner outlines, since it may not be obvious that the contours are different. I think this might turn out better with jigsaw nubs, but this is my first attempt, using Google draw with copy-paste.

I can (I think) standardize these tilings using something like the method in Tilings and Patterns (Grünbaum, Shephard). Since I'm not trying to classify a periodic tiling of one tile, I am abusing the notation a little, I think.

This is at least enough information to define appropriate contours between tiles to construct rhombus tilings representing plane partition height mod 2 (one flippable tile) and mod 4 (two flippable tiles) respectively.

In this notation, we follow boundaries clockwise and the arrow indicates if the edge is oriented the same or opposite. Its reflection will be the opposite direction arrow. We use + for edges that go in the clockwise direction and - for those that go opposite. We omit +/- if the boundary is symmetric for reflections.

I have also given the boundaries uppercase (lowercase) letters depending on whether they lie inside (outside) the original rhombus. This property, obviously, is conserved when flipping the tile.

In the case of one flippable tile, boundaries are symmetric, so arrows point both ways and there is no +/-: In the case of two flippable tiles, we need orientations. Boundaries match when both have the same clockwise or counterclockwise direction. The second tile reflects the a/A boundaries, making it possible to connect the tiles to their flipped orientations. A picture of the adjacencies, at the risk of turning it into spaghetti. I rotated the lower (flipped) tiles to remove some crossings. OK, what I really want here is to show just the original unflipped tiles, put edges between the matching boundary, and then label each edge with the transformation applied to the tile to make edges match up. That would also lend itself well to a backtracking tiling enumerator, though I have not used this method so far.

(Talking to myself here, but this is the sandbox. Is that OK? Maybe someone is interested.)

I wrote: OK, what I really want here is to show just the original unflipped tiles, put edges between the matching boundary, and then label each edge with the transformation applied to the tile to make edges match up.

The goal here is to provide tiles that identify the height mod k of the corresponding cubed plane partition using k colors.

These graphs capture the basic idea. In fact, there is no need to label edges with the transformation, because there are just two ways to match up edges and keep the tiles disjoint, and one of them requires flipping the tile. When the edges can be matched with (without) a flip, a red (black) edge is shown. The graph is just an illustration and the adjacencies can be written symbolically. Except for the bidirectional case, faces always match with opposite arrows.

Above shows (in order) one flippable tile for k=2, two flippable tiles for k=4, three non-flippable tiles for k=3, and three flippable tiles for k=6. I have not checked the last two carefully but they seem correct.

Since I was ordering other laser cuts, I threw in an easy one, and the results turned out really well. These are jigsaw pieces, mirror images of each other, that tile like oriented 60°-120° rhombuses. I was happy with the result, which interlocks and holds together even on thin material (1.3mm colored matboard). There's not much you can do with these except make (possibly decorative) designs. If you keep the same color, you have to rotate as you connect and they fit together in threes. If you want to keep connecting in a straight line, you have to alternate, and can make a skewed checkerboard this way. I would prefer these on a material that had a different color on each side to enforce the color/chirality relationship. These are "white" on the other side but they show some laser burns. Another idea is to glue them back to back. These pieces came out so well I'm reluctant to do that right now.