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

# Venn Diagram Survey Symmetric Diagrams

[symmetric diagrams | Gray codes ]

## Symmetric Venn diagrams

Here we (re-)show a Venn diagram made from 5 congruent ellipses. The regions are colored according to the number of ellipses in which they are contained: grey = 0, yellow = 1, red = 2, blue = 3, green = 4, and black = 5. Note that the number of regions colored with a given color corresponds to the appropriate binomial coefficient: #(grey) = #(black) = 1, #(yellow) = #(green) = 5, and #(red) = #(blue) = 10.

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.

#### n = 5

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].

#### n = 7

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.

### Representations of symmetric Venn diagrams

#### The Grünbaum encoding

The Grünbaum encoding of a simple symmetric Venn diagram consists of four n-ary strings, call them w, x, y, z, each of length (2n+1-4)/n. String w is obtained by starting with the outermost curve, following it in a clockwise direction, recording its intersections with the other curves, labelling them as they are first encountered, starting at 1. The other strings are obtained by going counter-clockwise and/or starting with one of the innermost curves. (Actually, Grünbaum proposed ordering the curves by their clock-wise appearance on the outer face; this amounts to a renumbering.) For the 3 circle diagram w = x = y = z = 1212. Each string of the encoding is a growth string [COS], meaning that each number is at most one greater than the values that precede it, with the first value being 0 (except that we take the first value to be 1). For the 5 ellipse diagram at the top of this page, the strings of the Grünbaum encoding are w = z = 123214121432 and x = y = 123414341214. Of course, we really only need two of the strings, one starting at the inside and one at the outside, since w can be inferred from x, and y from z -- but it's convenient to have all four, particularly when checking a diagram by hand. In fact, only one string is required, since, given x, the starting point of an inner string can be determined as the unique location where all curves have been encountered an odd number of times (thus implying that we're on the inside of all curves).

### Symmetric Venn diagrams with polar symmetry

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.

#### Symmetric monotone Venn diagrams without polar symmetry:

There are 23 known monotone symmetric Venn diagrams and 17 of these do not have polar symmetry.
• 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).

#### Symmetric non-monotone Venn diagrams:

There are no known symmetric non-monotone Venn diagrams with polar symmetry, but there are 33 known that do not have 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.

## Venn Diagrams and Gray Codes

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.

### A Phase Shifted Version of Edwards' Construction and Counting in Binary

Suppose that we rotate the jth curve in Edwards' general construction by pi/j radians. The result is still a Venn diagram, but it is no longer simple. The vertical line disappears into the horizontal line but the other curves remain distinct.
Aside from being attractive, the rotated version illustrates an interesting connection between the binary reflected Gray code and counting in binary. The binary reflected Gray code arises an a Hamilton path following two circles (picture) in the Venn graph of Edwards original construction. In the rotated version, with a minor modification, these same two circles may be traversed to count in binary (picture).

Edwards [Ed92] produced templates for making a rotatable Venn diagram; templates which we have scanned: page 1, page 2, page 3, page 4.

### Symmetric Venn diagrams and the Middle Two Levels problem

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!

### Symmetric Gray Codes?

Venn diagrams can lead to a highly symmetric Gray codes, if we exclude the bitstrings 0n and 1n. The idea is to find a Hamilton cycle that also exhibits a n-fold rotational symmetry, like that shown in the figure below.

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.

Block 1 Block 2 Block 3 Block 4 Block 5 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

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