Colloquium
3:00 p.m., Friday (November 24, 2006)
MATX 1100
Frank Ruskey
Dept. of Computer Science, University of Victoria, BC
Venn and Euler Diagrams: Recent Results and Open Problems
Venn and Euler diagrams are among the most wellknown of all
mathematical constructions. Perhaps surprisingly,
many fundamental questions about them are unresolved.
This talk will present an overview of recent research on
Venn and Euler diagrams, focusing on the following
open questions.
(0) Given a simple nVenn diagram is is always possible to
create a simple (n+1)Venn diagram by adding a new curve?
(1) A necessary condition for the existence of a rotationally
symmetric simple Venn diagram on n curves is that n be a prime
number. Is the condition sufficient?
(2) There is a 6Venn diagram of 6 triangles, but no
such 7Venn diagram. In general, given n, what is the least k
for which there exists an nVenn diagram of convex kgons?
(3) Given a set system S (i.e., a hypergraph) it is NPcomplete
to determine whether S has a rendering as an Euler diagram
where curves are allowed to intersect infinitely. Is the
question still NPcomplete if intersections must be finite?
(4) For n <= 7 it is possible to draw a minimum area Venn diagram
(in the rectilinear sense, so that curves must be polyominoes).
Is it possible in general?
The talk will be lavishly illustrated with colourful diagrams
and should be understandable by advanced undergrad students.
DEFINITIONS: An "nVenn" diagram is a collection of n simple closed
curves in the plane where all 2^n intersections of interiors/exteriors
of the curves are connected and nonempty. If the nonempty
condition is relaxed, you get the "nEuler" diagrams. If at
most 2 curves intersect at any point, the diagram is "simple".
Refreshments will be served at 2:45 p.m. (Lounge, MATX 1115).
