Coloring Penrose Tiles

In 1976, mathematicians Kenneth Appel and Wolfgang Haken proved the four-color theorem: Four colors are sufficient to color any map so that regions sharing a common border receive different colors (see Maps of Many Colors, Jan. 6, 1997).

There are, however, special cases in which fewer than four colors suffice. For example, it takes only two colors to fill in a checkerboard pattern. In fact, any planar map in which intersecting lines run from edge to edge, requires only two colors.

Example of a map that requires only two colors.

Placing ceramic tiles so that adjacent tiles have different colors suggests similar issues. It is certainly possible, for example, to use just two colors when setting square tiles in a checkerboard pattern. Three colors are needed for a honeycomb pattern of hexagonal tiles.

One particularly intriguing case involves so-called Penrose tilings. In 1974, mathematical physicist Roger Penrose of the University of Oxford discovered a set of two tiles that, when used together, cover a surface without forming a regularly repeating pattern. One tile resembles an arrowhead and is described as a dart, and the other tile looks like a diamond with one foreshortened end and is known as a kite. The two pieces fit together to form a rhombus.

A portion of a kite-and-dart Penrose tiling of the plane.

It turns out there are many different pairs of quadrilateral shapes that form a nonperiodic tiling pattern, though all are related in some way to the original kite-and-dart pair. One particularly striking set consists of a pair of diamond-shaped figures--one fat and one skinny.

A portion of a diamond-based Penrose tiling of the plane.

Attempts to color such Penrose diamond tilings led some people to conjecture that three colors suffice. Now, mathematicians Tom Sibley of Saint John's University in Collegeville, Minn., and Stan Wagon of Macalester College in St. Paul, Minn., have proved that to be the case. They go on to generalize the result to any map (or tiling) made up of parallelograms, as long as two adjacent countries (or tiles) meet in a single point or along a complete edge of the constituent pieces. The mathematicians describe such a map or pattern as "tidy."

Example of a three-colored Penrose diamond tiling.

The proof involves showing that, given a tidy finite map, a country has at most two neighbors.

The results, however, do not hold for all possible quadrilateral shapes and configurations. Moreover, no one has yet proved that Penrose kite-and-dart patterns require only three colors.

References:

Gardner, M. 1989. Penrose Tiles to Trapdoor Ciphers. New York: W.H. Freeman.

Hutchinson, J.P., and S. Wagon. 1998. Kempe revisited. American Mathematical Monthly 105 (February):170.

______. 1997. The four-color theorem. Mathematica in Science and Education 6 (No. 1):42.

Peterson, I. 1998. The Mathematical Tourist: New and Updated Snapshots of Modern Mathematics. New York: W.H. Freeman.

Sibley, T., and S. Wagon. Preprint. Three-coloring the Penrose rhombs.

Thomas, R. 1998. An update on the four-color theorem. Notices of the American Mathematical Society 45 (August):848.

Wagon, S. 1999. Mathematica in Action, 2nd ed. New York: Springer-Verlag.

Stan Wagon provided the Mathematica code for generating the illustrations of Penrose tilings.

Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org.