Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice

  • Jerrold Griggs
  • Charles E. Killian
  • Carla D. Savage

Abstract

We show that symmetric Venn diagrams for $n$ sets exist for every prime $n$, settling an open question. Until this time, $n=11$ was the largest prime for which the existence of such diagrams had been proven, a result of Peter Hamburger. We show that the problem can be reduced to finding a symmetric chain decomposition, satisfying a certain cover property, in a subposet of the Boolean lattice ${\cal B}_n$, and prove that such decompositions exist for all prime $n$. A consequence of the approach is a constructive proof that the quotient poset of ${\cal B}_n$, under the relation "equivalence under rotation", has a symmetric chain decomposition whenever $n$ is prime. We also show how symmetric chain decompositions can be used to construct, for all $n$, monotone Venn diagrams with the minimum number of vertices, giving a simpler existence proof.

Published
2004-01-02
Article Number
R2