January 11, 2003

Diagram Masters Cry ‘Venn-i, Vidi, Vici’

by Barry Cipra
Science magazine online

BALTIMORE, MARYLAND—Earlier this month, 5000 mathematicians converged here for the joint annual meetings of the American Mathematical Society and the Mathematical Association of America.

Some things are so simple you’d think they’d have nothing new to offer. Take Venn diagrams. A staple of high school algebra, these diagrams use overlapping geometric shapes usually circles — to represent the different ways two or three sets can intersect. What more is there to say?

A lot, it turns out. Three mathematicians, including an undergraduate student, recently solved a 3-decade-old problem involving rotationally symmetric Venn diagrams. Imagine making such a Venn diagram with a rubber stamp, moving the stamp evenly around a circle N times. The result would look like a daisy with N petals overlapping at the center. The hard part is finding a petal shape that will result in all possible combinations of intersections. For which numbers of sets (or petals), mathematicians wondered, can such rotationally symmetric diagrams be drawn? Only prime numbers work, they quickly realized, but which ones? Now Carla Savage and Charles “Chip” Killian of North Carolina State University in Raleigh and Jerrold Griggs of the University of South Carolina, Columbia, have found a way to draw a diagram for any prime number of sets, no matter how large.

Until 2 years ago, rotationally symmetric diagrams were known for only the first few primes. The familiar circular Venn diagrams with two and three sets fit the bill. There are many examples with five sets, including one made by rotating an ellipse (see figure), and many more with seven, although they were so hard to find that mathematicians initially doubted their existence. Two years ago, Peter Hamburger of Indiana University-Purdue University in Fort Wayne constructed an example for N = 11.

It looked as though mathematicians might be in for an eternity solving the problem prime by prime. Fortunately, the new result takes care of everything at once. At a workshop* held in Baltimore a few days before the joint math meetings, Savage and colleagues described a systematic way of producing rotationally symmetric Venn diagrams of arbitrarily large (prime) size. Their proof, which produces snowflakelike patterns that Hamburger calls “doilies,” builds on a suggestion Hamburger made after constructing his N = 11 example. “We didn’t have to do many new things,” Savage says. “When all the pieces were put together, it required only one new trick”: a clever way of ordering the intersections around the circle, which she credits to her then-student Killian (now a grad student at Duke University).

“The solution is very elegant,” says Lenore Cowen of Tufts University in Medford, Massachusetts. Frank Ruskey of the University of Victoria, Canada, whose Web site survey of Venn diagrams (sue.csc.uvic.ca/~cos/venn) has become a touchstone for researchers interested in the subject, agrees. “It’s nice to have it finally resolved,” he says.

The Carolina trio’s result is not the last word on Venn diagrams, though. Their construction produces points where many curves come together. Partly for aesthetic reasons, but mostly for a new challenge, mathematicians now want to know if they can find rotationally symmetric diagrams with curves that meet only in pairs. Examples are known with two, three, five, and seven sets, but whether that continues for larger primes—even 11 — remains to be seen.           

* ALICE03 (Algorithms for Listing, Counting, and Enumeration), 11 January; sponsored by the Society for Industrial and Applied Mathematics.

Copyright © 2003 by The American Association for the Advancement of Science. All rights reserved.

/ News Index / News Archives Index /