3:00 p.m., Friday (November 24, 2006)
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 well-known 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
(0) Given a simple n-Venn 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 6-Venn diagram of 6 triangles, but no
such 7-Venn diagram. In general, given n, what is the least k
for which there exists an n-Venn diagram of convex k-gons?
(3) Given a set system S (i.e., a hypergraph) it is NP-complete
to determine whether S has a rendering as an Euler diagram
where curves are allowed to intersect infinitely. Is the
question still NP-complete 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 "n-Venn" 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 non-empty. If the non-empty
condition is relaxed, you get the "n-Euler" 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).