THE ELECTRONIC JOURNAL OF COMBINATORICS 4 (1997), DS #5. |
This diagram has a very a pleasing symmetry, namely an n-fold rotational symmetry. Such diagrams are said to be symmetric. This simply means that there is a point x about which the diagrams may be rotated by 2ipi/n and remain invariant, for i=0,1,...,n-1. Any symmetric Venn diagram must be made from congruent curves.
A symmetric diagram need not be simple. Diagram #3.1 of Class 1 in the list of all Venn diagrams for n=3 is also a symmetric diagram, but it is not simple.
The ellipse diagram above has a 5-fold rotational symmetry. It is the only simple symmetric Venn diagram for n=5. There are non-simple symmetric diagrams for n=5 (6K), but their exact number is unknown.
Rick Mabry observes that the link of five knots formed by weaving the Venn diagram shown above is a Brunnian link --- the removal of any knot causes the link to fall apart. Mabry has created a beautiful rendering of the link made from ("ice cream cone curves"). This diagram serves as an illustration of a symmetric Brunnian link7 of order 5. (The usual depiction of the Borromean rings is a symmetric Brunnian link of order 3.) This Brunnian link is attributed to C. van de Walle by Stewart [St, pg. 106].
Referring to the case n=7, Grünbaum [Gr75,p.19] writes: "at present it seems likely that no such diagram exists." However, Grünbaum found examples of such diagrams [Gr92b] and in 1992 additional examples were also discovered by Anthony Edwards and independently by Carla Savage and Peter Winkler. One of Grünbaum's examples is a remarkable non-monotone symmetric Venn diagram. There are at least 17 other symmetric Venn diagrams for n=7 (these are all monotone).
Theorem. Symmetric Venn diagrams can exist only if n is a prime number.
This explains why we have only been discussing symmetric Venn diagrams for the values 3,5, and 7. To understand why the theorem is true, imagine the diagram to be split evenly into n sectors (pieces of pie). The C(n,k) 1 different regions representing the k-subsets must be evenly distributed in each of the n sectors. It thus follows that n divides C(n,k) for each k = 1,2,...,n-1. This divisibility restriction implies that n must be prime, via a theorem of Leibnitz [Ed96].
However, no one has ever discovered a symmetric Venn diagram for any prime larger than 7, and it remains a tantalizing puzzle to find one for n=11 or prove that none exists. Below we summarize what is know about symmetric Venn diagrams for n=7.
A symmetric Venn diagram has polar symmetry if it is invariant under "polar flips". Think of the diagram as being projected stereographically onto a sphere with the axis running thru the point of symmetry, and then project the diagram back onto the plane from the antipodal point on the axis. If the corresponding Venn graphs are isomorphic as plane graphs, then the diagram has polar symmetry. The unique symmetric Venn diagram for n = 5 has polar symmetry.
For n=7, all simple monotone symmetric Venn diagrams with polar symmetry are known; there are six of them, and they are listed below. The first five were discovered by Anthony Edwards using a program to generate candidate diagrams and manual checking to eliminate those candidates that were not Venn diagrams [Ed96]. He named them after the cities in which they were discovered and we follow his naming convention (but also number them P1-P6). Grünbaum [Gr92b] also discovered "Adelaide". An exhaustive computer search by Frank Ruskey uncovered another, "Victoria", that had been overlooked in Edwards manual checking.
There are many relations between Venn diagrams and (combinatorial) Gray codes. Some of these relations have not much to do with symmetry but some do.
Edwards [Ed92] produced templates for making a rotatable Venn diagram; templates which we have scanned: page 1, page 2, page 3, page 4.
For odd n = 2k+1 the middle two levels problem is to find a Hamilton path in the subgraph of the n-cube induced by those vertices corresponding to k-sets and (k+1)-sets. This is a well-known problem about which several papers have been written. Some symmetric Venn diagrams have embedded in them a solution to the middle two levels problem. For n=7 consider the diagrams Adelaide and Hamilton with the symmetric coloring. The middle two levels correspond to the middle two necklaces, the ones colored yellow (they also have diagonal line shading for those with black-and-white browsers). Note the zig-zag pattern that they follow, alternating between k-sets and (k+1)-sets. This is exactly a solution to the middle two levels problem.
It might be hoped that a general construction of symmetric Venn diagrams would give solutions to the middle two levels problem for n prime. However, a general construction of symmetric Venn diagrams seems very difficult, given that we can't find a single instance for n=11, so perhaps it's better to go the other way around. Maybe known solutions to the middle two levels problem for small values can give us insight into the construction of symmetric Venn diagrams!
Starting at the set {1}, and writing the bitstring representation of each subset we are lead to the table shown below (read down). Note that: (a) each of the 5 blocks is a right shift of the preceding block, (b) the columns are cyclicly equivalent (under a right shift of 6 bits), and (c) each block contains a representative of each non-trivial necklace of black and white beads. Such Gray codes are obviously balanced in the sense of Bhat and Savage [BS]; that is, each column has the same number of bit changes. It is easy to find symmetric Gray codes for n=7 using any of the Venn diagrams discussed earlier on this page.
10000 | 01000 | 00100 | 00010 | 00001 |
10100 | 01010 | 00101 | 10010 | 01001 |
11100 | 01110 | 00111 | 10011 | 11001 |
11110 | 01111 | 10111 | 11011 | 11101 |
11010 | 01101 | 10110 | 01011 | 10101 |
11000 | 01100 | 00110 | 00011 | 10001 |
Block 1 | Block 2 | Block 3 | Block 4 | Block 5 |
---|
THE ELECTRONIC JOURNAL OF COMBINATORICS 4 (1997), DS #5. |