Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice (Preprint)
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 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 B n, under the relation "equivalence under rotation" has a symmetric chain decomposition whenever n is prime. We also sho how symmetric chain decomposition can be used to construct, for all n, monotone Venn diagrams with the minimum number of vertices, giving a simpler existence proof.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2003
- Accession Number
- ADA640827
Entities
People
- Carla D. Savage
- Charles E. Killian
- Jerrola Griggs
Organizations
- University of South Carolina