\magnification=1200
\hsize=4in
\nopagenumbers
\noindent
{\bf Bette Bultena and Frank Ruskey}
\medskip
\noindent
{\bf Venn Diagrams with Few Vertices}
\vskip.5cm


An {\it $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 {\it weight} of a region is the number of curves that contain it.
A region of weight $k$ is a $k$-region.
A {\it 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$.


\bye