Monotone Venn Diagrams with Few Vertices

Bette Bultena, Department of Computer Science, University of Victoria, Canada.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.


The n-Venn diagram is a collection of n finitely-intersecting simple closed curves in the plane, such that each of the 2n sets formed by the n-fold intersections of {X1,X2,...,Xn}, where each Xi is the open interior or exterior of the i-th curve, is a non-empty connected region. The weight of a region is the number of curves that contain it. A region of weight k is a k-region. A monotone Venn diagram with n curves has the property that every region with weight k, where 0<k<n, is adjacent to at least one (k-1)-region and at least one (k+1)-region.

An n-Venn diagram can be interpreted as a planar graph in which the intersection points of the curves are the vertices. For general Venn diagrams, the number of vertices is at least the ceiling of (2n-2)/(n-1). Examples are given that demonstrate that this bound can be attained for 1 < n < 7. We show that each monotone Venn diagram has at least C(n,n/2) vertices, and that this lower bound can be attained for all n > 1.

The diagram above is the same as Figure 7 in the paper except that the resulting saturating symmetric chains have been overlaid. It is easy to see that the chains produced and their linear placement in the plane is exactly that given by the "Christmas tree pattern" discussed by Knuth in pre-fascicle 4A (pages 17-20 in the version of March 31, 2005). This symmetric chain decomposition was discovered by de Bruijn, van Ebbenhorst Tengbergen, and Kruyswijk (Niew Archief voor Wiskunde 23 (1951) 191-193).

Back to list of publications.