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 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 open questions.

(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).