Half-Simple Symmetric Venn Diagrams

  • Charles E. Killian
  • Frank Ruskey
  • Carla D. Savage
  • Mark Weston

Abstract

A Venn diagram is simple if at most two curves intersect at any given point. A recent paper of Griggs, Killian, and Savage [Elec. J. Combinatorics, Research Paper 2, 2004] shows how to construct rotationally symmetric Venn diagrams for any prime number of curves. However, the resulting diagrams contain only ${n \choose {\lfloor n/2 \rfloor}}$ intersection points, whereas a simple Venn diagram contains $2^n-2$ intersection points. We show how to modify their construction to give symmetric Venn diagrams with asymptotically at least $2^{n-1}$ intersection points, whence the name "half-simple."

Published
2004-11-30
Article Number
R86