THE ELECTRONIC JOURNAL OF COMBINATORICS 4 (1997), DS #5. |

Symmetric Diagrams

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 2*i***pi**/*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 link^{7}
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.

**Adelaide (P1):**Info, black-and-white , one curve colored , symmetric coloring , rainbow coloring , Edwards' rendering (149K).**Hamilton (P2):**black-and-white , one curve colored , symmetric coloring , rainbow coloring .**Massey (P3):**black-and-white , one curve colored , symmetric coloring , rainbow coloring .**Victoria (P4):**black-and-white , one curve colored , symmetric coloring , rainbow coloring , alternate coloring .**Palmerston North (P5):**black-and-white , one curve colored , symmetric coloring , rainbow coloring .**Manawatu (P6):**black-and-white , one curve colored , symmetric coloring , rainbow coloring .

- A list of the 17 known monotone symmetric Venn diagrams without polar symmetry. We believe that these are all of them.
- A symmetric diagram whose curves are 5-gons. This diagram is from [Gr92b] and is M2 on our list.
- A list of all 23 known monotone Venn diagrams (includes the six with polar symmetry).

- Grünbaum's non-monotone symmetric diagram, in black-and-white (scanned from [Gr92b]) and in color.
- Another non-monotone symmetric Venn diagram; this one discovered by Chow and Ruskey. A colored rendering.
- A list of the Grünbaum representations of the 33 known non-monotone symmetric Venn diagrams. We believe that these are all of them. None have polar symmetry. Grünbaum's example shown above is number 27 in the list and the other one shown above is number 33.
- Tutte embeddings of diagrams N1, N2, N3, N4, N5, N7 from the above list.
- Colored Tutte embeddings of diagrams N1 and N7 from the above list.

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.

*n*= 2: black and white, colored.*n*= 3: black and white, colored.*n*= 4: black and white, colored.*n*= 5: black and white, colored.*n*= 6: black and white, colored.- animated for
*n*=2..6.

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* = 2*k*+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. |