THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5.

Venn Diagram Survey
Symmetric Diagrams, Necklaces, and Chains

[necklaces | construction ]

Using Necklaces

The Venn diagram, discovered by Stirling Chow and the first author in 1996, and shown here has a number of remarkable properties. First, it has the least number of vertices among all monotone 5-Venn diagrams by a result of [BR]. Secondly, two cut-vertices delimit a 1/n sector which can be rotated to get the full diagram. Of course, the labels on the curves must also be "rotated." The same principles used to discover this diagram can be used to obtain similar 7-Venn diagrams, such as the discovered by the author in 1997 and shown below; the same ideas were used by Hamburger in discovering his diagram for n=11 and by Griggs, Killian and Savage in their amazing construction for symmetric diagrams for all prime n, discussed later on this page.

Recall that a necklace is an equivalence class of strings under rotation. Here the strings are binary; i.e., taken over the two letter alphabet {0,1}. Since n is prime each of the n rotations is distinct (if the string is not either all 0s or all 1s).

Below we show a lattice of necklaces, the ranks of the lattice giving the number of black beads (the all yellow and all black necklaces have been omitted). The relation is subset inclusion on the black bead numbers. Each cover relation of the lattice has been labelled with the number of the bead that changes. The lattice now has the property that every path from the top to the bottom is a permutation of 1,2,...,7. These properties are sufficient to allow us to construct a Venn diagram.

Consider each necklace to be a vertex in the dual graph as shown in the figure to the right. The edge numbering allows us to draw n curves from left-to-right; curve 2 has been colored red. Copying this seven times results in the Venn diagram shown at the bottom of the page. The curves are renumbered in each successive pie-slice by adding 1 (mod n). Curve one has been colored in green. Note that curve 2 in the defining pie-slice has become curve 1 in the second pie slice, and so on.

When will the resulting diagram have the least number of vertices? Exactly when the middle two levels of the lattice diagram form a perfect matching, as they do here.

   

The corresponding sector of the diagram.

The lattice of necklaces forming the dual of 1/nth of a Venn diagram.    

The resulting diagram, in its entirety, formed by rotating the sector.

Note that not all monotone symmetric Venn diagrams with the least number of vertices can be constructed using these methods: see this example.

The [GKS] Construction

Using ideas similar to those above, Jerrold Griggs, Chip Killian, and Carla Savage [GKS] produced a construction for a symmetric Venn diagram for any prime n. The difficult part is constructing a plane embedding of a lattice of necklaces such that every string of length n is represented exactly once by a necklace. We start by illustrating how to build chains of n-bit strings, and then show how to link them up to form a dual graph like the one above.

In a binary string, regard each `1' as a right parenthesis and each `0' as a left parenthesis and then match parentheses in the usual way. For example, in the string

1 0 0 1 0 0 1 1 1 1 0 0 1 0
) ( ( ) ( ( ) ) ) ) ( ( ) (

the parentheses in green are matched with the parentheses in red. The black 1s and 0s are unmatched. Then chains of strings can be formed by using the Greene-Kleitman successor rule:

Starting with a string x, change the first unmatched 0 in x to a 1 to get its successor y.
In the example above, the string 10010011110010 becomes 10010011111010. Greene and Kleitman showed in [GK] that, if the strings chosen to start the chains are exactly those with no unmatched 1, then the resulting chains (formed by applying the above rule successively to each chain starter until there are no unmatched 0s) form a symmetric chain decomposition of the Boolean lattice. That is, every n-bit string will occur exactly once in the resulting chains.

Griggs, Killian, and Savage use this rule to construct a symmetric chain decomposition of only 1/nth of the strings to form a necklace diagram like that above. They build a set Rn with size (2n - 2)/n, consisting of necklace representatives. To choose the appropriate representatives, they use the notion of a block code for an n-bit string: let x be an n-bit string. If x begins with 0 or ends with 1, the block code is infinity. Otherwise, x consists of some number of blocks of the form 111 ...1000...0, and the block code is simply the sequence of the lengths of these blocks.

For example, the block codes of the string 1100100 and all of its 7 rotations are shown below:

bitstring block code
1100100 (4, 3)
1001001 infinity
0010011 infinity
0100110 infinity
1001100 (3, 4)
0011001 infinity
0110010 infinity

For each n-bit string, the rotation chosen as the representative in Rn is that which has the lexicographically-least block code. For example, for the string above, the rotation 1001100 is the choice to be in Rn. The authors of [GKS] show that this rule results in exactly one necklace representative for each equivalence class of strings under rotation, which is unique since n is prime.

Given Rn, the chains are built using this variation of the Greene-Kleitman successor rule:

Start with a string x in Rn with exactly one unmatched 1 (which must be in the first position). If there are at least two unmatched 0s in x, change the first unmatched 0 to 1 to obtain the successor of x. Continue until a string with only one unmatched 0 is reached.
It is shown in [GKS] that this gives a symmetric chain decomposition of the subset of the Boolean lattice defined by Rn. The chains so constructed are illustrated below as vertical columns of strings connected by thick black edges.

The dual of the Venn diagram is formed by imposing a tree structure on the set of chains. Identify each chain with its chain starter (i.e., the string with exactly one unmatched 1). The root of the tree is 10n-1, from the unique chain with n-1 elements. The parent of other chain starters is obtained by changing the rightmost 1 into a 0. For n = 7 the tree so constructed is illustrated below with the green edges. To obtain the dual a symmetric tree is formed from the final elements in the chains (strings with one unmatched 0). These edges of this symmetric tree are shown in blue below for n = 7. The dual graph of a sector like those above can now be created by embedding in the plane the tree as defined, embedding each chain vertically starting from the nodes in the tree, and then embedding the tree attached to the final elements in the chains. The figure below (minus the red edges) shows the plane graph that results from the construction for n=7.

This graph can be turned into a symmetric 7-Venn diagram by the process illustrated in the first section on this page.

In [KRSW] the authors showed that more edges can be added to add vertices to the resulting Venn diagram. In the graph constructed above, the face formed between each chain and the child chain embedded immediately beside it can have edges added; the number of extra edges is equal to one less than the number of elements in the shorter chain. In the figure above, the red edges are extra edges that can be added between adjacent chains.

THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5.