Venn diagrams with few vertices

Bette Bultena ; Frank Ruskey

The electronic journal of combinatorics, Tome 5 (1998)

Résumé

An $n$-Venn diagram is a collection of $n$ finitely-intersecting simple closed curves in the plane, such that each of the $2^n$ sets $X_1 \cap X_2 \cap \cdots \cap X_n$, where each $X_i$ 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 $k$-region, where $0 < k < n$, is adjacent to at least one $(k-1)$-region and at least one $(k+1)$-region. Monotone diagrams are precisely those that can be drawn with all curves convex. 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 $ \lceil {2^n-2 \over n-1} \rceil$. Examples are given that demonstrate that this bound can be attained for $1 < n \le 7$. We show that each monotone Venn diagram has at least ${n \choose {\lfloor n/2 \rfloor}}$ vertices, and that this lower bound can be attained for all $n > 1$.

Détail

DOI : 10.37236/1382

Classification : 05C10, 52C99
Mots-clés : Catalan number, convex curve, dual graph, closed curves, Venn diagram, planar graph