 THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5.  # Venn Diagram Survey Examples of Symmetric Diagrams for small n

[ n=5 | n=7 | n=11 ]

On this page we show many examples of symmetric Venn diagrams for 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.

# n = 5

The simple ellipse diagram, from [Gr75], has a 5-fold rotational symmetry. It is the only simple symmetric Venn diagram for n=5; here are several different renderings of it:

• 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".
• A version created by the author is here; 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].
• A rendering of the diagram using 5 equilateral triangles is given by Grünbaum in [Gr92b] and redrawn here.
• Stuart Anderson provided us with the labelled Tutte embedding11 of the diagram; one curve is highlighted.
There are many non-simple symmetric diagrams for n=5. The one shown here is a play on the result that Venn diagrams cannot 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.

Here is a non-simple diagram, redrawn from [Gr75], that shows that rectangles can be used - though the figures look like squares, they are slightly longer in one dimension, and in fact Grünbaum conjectured that a 5-Venn diagram of squares does not exist, simple or not.

We have done an exhaustive computer search of all symmetric Venn diagrams for n = 5 (first reported in the 1997 version of this survey). 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 total rigid 10 15 20 25 30 72 111 49 10 1 6 12 12 0 1

# n = 7 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 himself later 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 simple symmetric Venn diagram. There are 23 simple monotone symmetric Venn diagrams for n=7. Below we summarize what is know about symmetric Venn diagrams for n=7.

#### 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 first numbering the curves clockwise as they appear on the outer face, and then following curve n, recording its intersections with each of the other curves. The other strings are obtained by going counter-clockwise and/or starting with one of the innermost curves; in each case the curves must be re-numbered first. For the 3 circle diagram w = x = y = z = 1212. For the 5 ellipse diagram at the top of this page, the strings of the Grünbaum encoding are
w = z = 142413141324 and
x = y = 132414241314.
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. How can x be obtained from w in general? Think of the strings as being indexed i = 1,2,...,M. The rule is x[i] = n-w[M-i+1].

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.

This encoding scheme has its parallels in other disciplines: topologists may recognise the Grünbaum encoding as being closely related to the Gauss code of a knot10.

Tao Cao proved in [Cao] that for simple symmetric monotone Venn diagrams the Grünbaum encoding uniquely identifies the diagram (up to isomorphisms).

### Simple Symmetric Diagrams for n = 7

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]; however one, Hamilton, was found by hand. 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 simple monotone Venn diagrams without polar symmetry:

There are in total 23 monotone symmetric Venn diagrams and 17 of these do not have polar symmetry.

#### Symmetric simple non-monotone Venn diagrams:

There are no known symmetric non-monotone Venn diagrams with polar symmetry, but there are 33 known simple diagrams that do not have polar symmetry. We believe that these are all of the simple symmetric non-monotone diagrams for n=7.
• 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.

### Non-simple symmetric diagrams for n = 7

All of the diagram construction methods for non-simple diagrams employed by the author 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. The following page illustrates these ideas more concretely, and shows how they were used by the authors of [GKS] to create a general construction for symmetric Venn diagrams for any n:

From computer searches it is apparent that there are many more non-simple diagrams than there are simple diagrams. Using the above techniques, in [Wes] the authors generated hundreds of thousands of distinct non-simple monotone symmetric 7-Venn diagrams, including 1576 rigid diagrams (both polar symmetric and not).

#### Minimum vertex symmetric diagrams

For n = 7, the value ceiling[ (2n-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 are linked below.

Hamburger and Pippert, in [HP03], using different methods than those above, also constructed a minimum-vertex non-monotone symmetric 7-Venn diagram with several nice features. Their diagram is not rigid either.

# n = 11 Peter Hamburger [Ha02] constructed the first 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 symmetric diagrams and necklaces page, 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 this page. Successive sectors may be obtained from this one by cyclicly permuting the colors.

Linked below are various other renderings of the first symmetric 11-Venn diagram.

The construction method for this diagram uses a partition of the set of all bitstrings of length 11. Recall that the Venn dual can be labelled with bitstrings corresponding to regions, as we discussed on the page Graphs Associated with Venn Diagrams. The construction then uses chains of bitstrings connected together to build the large dual graph of the sector, which then is repeated to give the entire diagram.

Since the diagram is highly non-simple and not rigid, the diagram can be turned in to many others by separating any or all separable vertices. Hamburger has published variants of the diagram with vertex sets from 462 up to 1001 by increments of 11 in [Ha02b]. He and other co-authors have used similar techniques to create other diagrams; see the sub-sections below.

To date, the only other group to have constructed a symmetric 11-Venn diagram is Griggs, Killian, and Savage [GKS]; their diagram is below. The sector forming 1/11th of the diagram is illustrated below; notice that unlike Hamburger's diagrams the sector has a vertical symmetry in that it maps onto itself, ignoring colours, by reflection about a horizontal axis - this is a nice feature of the construction in general. For more details on the construction methods used for these diagrams, see the page Symmetric Diagrams, Necklaces, and Chains.

#### Simple symmetric diagrams

Though no simple symmetric 11-Venn diagram has been discovered yet, Hamburger, Petruska, and Sali [HPS] have come close by finding a diagram with 1837 vertices - 209 fewer than the maximum possible of 2046. Their construction is an extension of the above method, hinging on finding paths of vertices through planar spanning subgraphs of the hypercube. The resulting diagram is non-monotone.

#### Minimum vertex symmetric diagrams

For n = 11, the minimum possible number of vertices is ceiling[ (211 - 2) / 10 ] = 205. This is not divisible by 11, and the smallest number of vertices possible in a symmetric 11-Venn diagram is 209. In [HS03] Hamburger and Sali extended their above method to produce a diagram with 231 vertices, quite close to the minimum possible, and then later found a diagram with 220 vertices (as yet unpublished - thanks to Peter Hamburger for showing us the diagram). The resulting diagrams are highly non-monotone.

Many of the symmetric 11-Venn diagrams mentioned here, in papers by Peter Hamburger and his co-authors, have been turned into works of art by the artist Edit Hepp. Readers are encouraged to seek out the papers in print to view the diagrams. The processes used to create the artwork are explained in [HH].