THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. March 2001), 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.

The purpose of this section is to survey what is known about symmetric diagrams. We begin with a simple necessary condition.

**Theorem.**
A necessary condition for the existence of a symmetric *n*-Venn
diagram is that *n* be a prime number.

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

Although symmetric diagrams are known for *n* = 2,3,5,7, and 11
none is known for *n* = 13 or any larger prime.
There is one other symmetry that we will consider for diagrams drawn
in the plane.

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 symmetric Venn diagram shown above has polar symmetry, although it
is perhaps not readily apparent.

We will now consider specific values of *n*.
For *n* = 2, there is only one Venn diagram and it can be drawn
to be polar symmetric.
For *n* = 3, there are two symmetric diagrams.
The classic three circle diagram is monotone, simple, and has
polar symmetry.
Diagram #3.1
of Class 1 in the list of all Venn diagrams for *n*=3
is also a polar symmetric diagram, but it is not simple, nor is it rigid.

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.
The one shown here is a play
on the result that Venn diagrams can not be constructed from
"curves that are" circles for *n* > 3; a statement
that is no longer true if the three words in quotation marks
are removed.

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").
Another one created by the author is
here.
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].

We have done an exhaustive computer search of all symmetric Venn
diagrams for *n* = 5.
The number of symmetric Venn diagrams for *n*=5 is 243,
and the table below shows the number possessing particular
attributes.
It is a trivial matter to construct non-simple diagrams from
simple ones by "pinching together" simple intersections,
but this operation does not produce an essentially different
diagram.
Thus we are particularly interested in rigid diagrams,
of which there are 12+13+2+4 = 31.

Polar | Rigid | Monotone | Count |
---|---|---|---|

no | no | no | 100 |

no | no | yes | 89 |

no | yes | no | 12 |

no | yes | yes | 13 |

yes | no | no | 5 |

yes | no | yes | 18 |

yes | yes | no | 2 |

yes | yes | yes | 4 |

For *n*=5, a symmetric minimum Venn diagram must have at
least 10 vertices.
There are exactly six symmetric rigid Venn diagrams with 10
vertices for *n* = 5.
One of them is shown below.
(MinSymm5a.gif,
MinSymm5b.gif,
MinSymm5c.gif)

The following table shows the number of symmetric diagrams classified according to the number of vertices and rigidity.

vertices | 10 | 15 | 20 | 25 | 30 |
---|---|---|---|---|---|

total | 72 | 111 | 49 | 10 | 1 |

rigid | 6 | 12 | 12 | 0 | 1 |

Referring to the case *n*=7, Grünbaum [Gr75,p.19] wrote:
"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 17 simple monotone symmetric Venn
diagrams for *n*=7.
Below we summarize what is know about symmetric Venn diagrams for
*n*=7.

Of course, we really only need two of the strings, one starting at the inside and one at the outside, sincew=z= 142413141324 and

x=y= 132414241314.

In fact, only one string is required, since string **y** is a circular
rotation of **x**.
The starting position of **y** can be determined as the unique position
in **x** where all curves have been encountered an odd number of times
(thus implying that we're on the inside of all curves).
In the 5 ellipse example, the starting position of **y** is the rightmost
1 in **x**.
If a single string is chosen to be the representative, then we take the
lexicographically least of all four.

A closely related encoding is the *G-encoding* which is obtained
by following a curve from the interior/exterior face, numbering and
recording the curves in the order that they are encountered.
Each string of the encoding is a restricted
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).
The four strings corresponding to the 5 ellipse example are:

w=z= 123214121432 and

x=y= 123414341214.

For monotone diagrams the Grünbaum encoding uniquely identifies the diagram, and we believe that this is the case for the G-encoding and non-monotone diagrams.

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), Tutte embedding , Tutte embedding (one curve colored), link rendering .**Hamilton (P2):**black-and-white , one curve colored , symmetric coloring , rainbow coloring . Tutte embedding , Tutte embedding (one curve colored), link rendering .**Massey (P3):**black-and-white , one curve colored , symmetric coloring , rainbow coloring , Tutte embedding , Tutte embedding (one curve colored), link rendering .**Victoria (P4):**black-and-white , one curve colored , symmetric coloring , rainbow coloring , alternate coloring , animated one curve colored, Tutte embedding , Tutte embedding (one curve colored), link rendering .**Palmerston North (P5):**black-and-white , one curve colored , symmetric coloring , rainbow coloring , Tutte embedding , Tutte embedding one curve colored), link rendering .**Manawatu (P6):**black-and-white , one curve colored , symmetric coloring , rainbow coloring , Tutte embedding , Tutte embedding (one curve colored), link rendering .

- A list of the 17 monotone symmetric Venn diagrams without polar symmetry.
- A symmetric diagram whose curves are 5-gons. This diagram is from [Gr92b] and is M2 on our list.
- A list of all 23 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 G-encodings of the 33 known non-monotone symmetric Venn diagrams. 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.

From computer searches it is apparent that there are many more non-simple diagrams than there are simple diagrams. We show just a few of them in this section and point out an interesting connection between diagrams and necklaces.

All the diagram construction methods employed by the author,
for both simple and non-simple diagrams rely
on constructing a 1/*n* pie-slice of the diagram, which is
then rotated *n* times to get the full diagram.
Any pie slice whose boundary doesn't include any intersection
points induces a permutation of the curves of the diagram.
Since the *n*-fold composition of that permutation must be
the identity and *n* is prime, it follows that the permutation
must be circular.
This necessary condition is useful in testing whether a pie-slice
could be part of a diagram.
Furthermore, if the pie slice is taken so as to not bisect any
region, other than the inner and outer regions, then the regions
in the pie slice must be inequivalent under rotation.
Some of these ideas are illustrated on the following page:

For *n* = 7, the value
*ceiling*((2^{n}*-*2)/(*n-*1))
is divisible by 7, which leaves open the possibility that there is a
minimum vertex symmetric Venn diagram in which every curve passes through
every vertex.
In fact, we have discovered 60 such diagrams, but all
discovered so far are non-rigid.
Illustrations of two of them may be obtained from the list below.

Recently, Peter Hamburger
[Ha01]
has constructed a symmetric Venn
diagram for *n*=11.
The diagram is monotone and highly non-simple.
It is very similar in form to the diagram for *n*=7
shown on the
`VennNecklaceEJC.html`
page above, but is vastly more complicated because
of increase in the the number of regions, intersection points, etc.
In fact, the diagram is so intricate, that it is difficult
to show in a single figure.
One sector of the diagram is shown above;
the others may be seen on the page
`VennSymm11EJC.html`.
Successive sectors may be obtained from this one by
cyclicly permuting the colors.
Below we show illustrate various other renderings of this diagram.

- The entire diagram together with a a larger version.
- One curve; the entire diagram may be obtained by rotating this curve 11 times. Here's a larger version.
- The pie-slice (sector 1); the entire diagram may be obtained by rotating this diagram 11 times, on each successive rotation, relabelling the curves by the circular permutation (1 2 3 4 5 6 7 8 9 10 11). Here's a larger version.

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 only one example is known for
*n*=11, and none for any larger prime,
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.
Gray codes with property (b) are said to be *single-track*.
For more on single-track Gray codes see Hiltgen and Paterson, and Brandestini
[HPB].

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 (ed. March 2001), DS #5. |