|
| THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. March 2001), DS #5. |
The Venn diagram, discovered by the author and Stirling Chow 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 [BuRu]. 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 discoverd by the author in 1997 and shown below; and by Hamburger in discovering his amazing diagram for n=11.
Recall that a necklace is an equivalence class of strings under rotation. Here the strings are binary; i.e., taken over a two letter alphabet. Since n is prime each of the n rotations is distinct.
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 relations are a subset of the subset inclusion relationship 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 2-nd 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 ELECTRONIC JOURNAL OF COMBINATORICS (ed. March 2001), DS #5. |
