Discrete Mathematics and Optimization Seminar

Frank Ruskey
University of Victoria
Monday March 15th at 4.30pm
Burnside 1205



Title. Recent Results about Symmetric Venn Diagrams.

Abstract. We first present a general overview of Venn diagrams and their properties and uses, focusing on
diagrams with rotational symmetry, which can be quite beautiful. We then discuss some recent results about
Venn diagrams.Killian, Griggs, and Savage proved that symmetric Venn diagrams exist if and only if the number
of curves, $n$, is prime. However, the resulting diagrams are highly non-simple, where a simple diagram is one
with at most two curves passing through any point.In fact, the KGS diagrams are minimal with respect to number
of intersection points within the class of diagrams drawable with convex curves, since they have ${n \choose n/2}$ points of
intersection. We show how to modify their construction so that the resulting diagrams are ``half-simple" in the sense
of having asymptotically $2^{n-1}$ points of intersection, whereas a simple diagram has $2^n-2$ points of intersection.
Time permitting, we also present some recent constructions of pseudo-symmetric and area-proportional Venn diagrams.