THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5. |
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.
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 |
) | ( | ( | ) | ( | ( | ) | ) | ) | ) | ( | ( | ) | ( |
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 R_{n} with size (2^{n} - 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 R_{n} is that which has the lexicographically-least block code. For example, for the string above, the rotation 1001100 is the choice to be in R_{n}. 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 R_{n}, the chains are built using this variation of the Greene-Kleitman successor rule:
Start with a string x in R_{n} 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 R_{n}. 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 10^{n-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. |