tailieunhanh - Báo cáo toán học: "Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice. | Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice Jerrold Griggs Charles E. Killian Department of Mathematics Department of Computer Science Box 8206 University of South Carolina North Carolina State University Columbia SC 29208 Raleigh NC 27695 griggs@ chip_killian@ Carla D. Savage t Department of Computer Science Box 8206 N. C. State University Raleigh NC 27695 savage@ Submitted Aug 30 2002 Accepted Dec 11 2003 Published Jan 2 2004 MR Subject Classifications 03E99 05610 06A07 06E10 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 Bn and prove that such decompositions exist for all prime n. A consequence of the approach is a constructive proof that the quotient poset of Bn 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. Research supported in part by NSF grant DMS-0072187. 1 Research supported by NSA grant MDA 904-01-0-0083 THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R2 1 1 Introduction Venn Diagrams Following Griinbaum Gru75 an n-Venn diagram is a collection of n simple closed curves in the plane 1 2 . n with the property that for each S Q 1 2 . n the region int i n ext i its i s is nonempty and connected where int i and ext i denote the interior and exterior respectively of i. For this paper we require that any two of the curves i intersect in only a finite number of points. Figure 1 shows four 3-Venn diagrams b c and d are from CHP96 . A .