The Weekly Newsmagazine of Science
Recently on MathTrek:
May 15, 1999
|<<Back to Contents|
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. 4, 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.
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.
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.
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."
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.
Comments are welcome. Please send messages to Ivars Peterson at firstname.lastname@example.org.
Ivars Peterson is the mathematics/computers writer and online editor at Science News. He is the author of *The Mathematical Tourist, Islands of Truth, Newton's Clock, Fatal Defect, and The Jungles of Randomness. His current work in progress is Fragments of Infinity: A Kaleidoscope of Mathematics and Art (to be published in 1999 by Wiley).
MATHEMUSEMENTS: Look for math-related articles by Ivars Peterson every month in the children's general-interest magazine Muse (http://www.musemag.com) from the publishers of Cricket and Smithsonian magazine.
Back to Top
Copyright © 1999 Science Service