Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: Half-Simple Symmetric Venn Diagrams. | Half-Simple Symmetric Venn Diagrams Charles E. Killian Department of Computer Science Duke University Durham NC ckillian@cs.duke.edu Carla D. Savage t Department of Computer Science North Carolina State University Raleigh NC savage@csc.ncsu.edu Frank Ruskey Department of Computer Science University of Victoria Victoria BC Mark Weston Department of Computer Science University of Victoria Victoria BC mweston@cs.uvic.ca Submitted Sep 9 2004 Accepted Oct 13 2004 Published Nov 30 2004 Mathematics Subject Classifications 05A10 05A16 06A07 06E10 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 Qn 2j intersection points whereas a simple Venn diagram contains 2 2 intersection points. We show how to modify their construction to give symmetric Venn diagrams with asymptotically at least 2n-1 intersection points whence the name half-simple. 1 Introduction Following Grunbaum 5 a Venn diagram for n sets is a collection of n simple closed curves in the plane O1 O2 . O with the property that for each S c 1 2 . n the region int Oi n ext i i2S i2S is nonempty and connected. Here int i and ext t denote the open interior and open exterior respectively of i. A Venn diagram is simple if no 3 curves have a common point of intersection. In a Venn diagram the curves are assumed to be finitely intersecting. A Venn diagram is rotationally symmetric if there is a point p such that each of the rotations Research supported in part by NSERC grant 0-GP-000337999 Research supported in part by NSF grant DMS-0300034 and NSA grant MDA 904-01-0-0083 THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R86 1 of 1 about p by an angle of 2 II 0 i n 1 coincides with one of the curves 1 2 . n. A Venn diagram is monotone if every region enclosing k curves
