 THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5.  # Venn Diagram Survey Open Problems

## Open problems related to Venn diagrams.

#### Combinatorial Problems

• Is it true that every simple Venn diagram of n curves can be extended to a simple Venn diagram of n+1 curves by the addition of a suitable curve? [That this is true is a conjecture of Winkler [Wi]. It was proven to be true for not necessarily simple Venn diagrams by Chilakamarri, Hamburger, and Pippert [CHP96a].] Equivalently: Is every planar dual graph of a simple Venn diagram Hamiltonian?

• Find a simple symmetric 11-Venn diagram. More generally, find a general construction for simple symmetric Venn diagrams.

• Find a minimum-vertex symmetric 11-Venn diagram. Such a Venn diagram would have 209 vertices.

• Find a polar symmetric 11-Venn diagram.

• How many symmetric Venn diagrams are there for n = 5? There is only one symmetric simple 5-Venn diagram.

• How many symmetric Venn diagrams are there for n = 7? It is known that there are at least 33 simple symmetric Venn diagrams.

• Find a Brunnian link whose minimal projection is a symmetric Venn diagram of order 7 or prove that no such link exists.

• For n > 2, find a "symmetric" diagram on the sphere where the group of symmetries is different than those used in the section on symmetric Venn diagrams. In that section the group of symmetries consisted of rotations about a single axis, or rotations and a flip about that axis. In other words, the problem is: Are there other groups of isometries that act transitively on the curves of some Venn diagram on the sphere?

• The least number of vertices in a monotone Venn diagram is known to be C(n,n/2); what is the least number of vertices in a general Venn diagram? The lower bound of ceiling[ (2n-2)/(n-1) ] is known to be achievable for n < 8, so the first open case is n = 8. It is not known whether there is a rigid minimum vertex Venn diagram for n = 7.

• Find a construction for rigid* monotone n-Venn diagrams with C(n,n/2) vertices. The constructions of [BGR] and [GKS] have C(n,n/2) vertices but have many separable vertices. Examples for n=7 are known.

• The dual of a simple Venn diagram is a maximal planar spanning subgraph of the hypercube. (The dual is still maximal if the Venn diagram is only rigid.) Does every maximal planar 3-connected spanning subgraph of the hypercube, where all faces are quadrilaterals, occur as the dual graph of some simple Venn diagram?

#### Geometric Problems

• For every n, is there a convex Venn diagram made from congruent curves? That this is possible if the curves are allowed to intersect in segments was shown in the section on infinitely intersecting Venn diagrams. This is known to be true for primes by the [GKS] construction and for n = 4 (which can be done with congruent ellipses), but is open for other values of n.

• Find a general construction for minimum-area "Venn" diagrams made from polyominoes. The largest value of n for which a poly-Venn is known to exist is n = 7.

• Find a 6-Venn diagram in which each curve is a rectangle; this problem is from Grünbaum [Gr84b]. Slightly easier, find a 6-Venn diagram in which each curve is a trapezoid. His other problem of finding a 6-Venn diagram in which each curve is a triangle has been answered affirmatively. See the six amazing triangles.

• Find a 6-Venn diagram made from equilateral triangles. Even the problem of finding a 6-independent family made from equilateral triangles is open. This problem is from Grünbaum [Gr75].

• As shown on this page, there is no simple Venn diagram of 8 convex quadrilaterals. Does there exist a Venn diagram of 8 quadrilaterals not required to be convex or simple, or of 8 pentagons? These problems are due to Grünbaum.

• As a function of n, what is the maximum value, taken over all simple convex n-Venn diagrams, of the minimum k necessary to draw the diagram as a collection of convex k-gons? For example, for n=7 we know that there exists a simple diagram (namely, Victoria) that is drawable with convex 4-gons. However, we suspect that other diagrams are not drawable with 4-gons, but since they are convex they are drawable by k-gons, for some k < 126. What is the maximum k over all 7-Venn diagrams? More generally what is the value of k for n-Venn diagrams? By the results of [BGR], any convex Venn diagram can be drawn with (2n-2)-gons. Can every convex 3-Venn diagram be drawn with ellipses or triangles?

• Over all n-Venn diagrams, which requires the greatest number of straight line segments to draw it?

#### Generalizations of Venn Diagrams

• Find a symmetric k-fold (k > 2) Venn diagram on the sphere or prove that no such diagram exists. For n = 2 there are diagrams that, in the plane, have rotational symmetry, and examples that have mirror-image symmetry (these examples due to Branko Grünbaum [FGK]).

• Prove that there do not exist simple symmetric independent families or simple symmetric near-Venn diagrams attaining the bounds given on the Generalizations and Extensions page (the numbers I(n) and E(n) give these bounds).

• Generalize the result of [GKS] (described on this page) to find a general construction for symmetric independent families and/or near-Venn diagrams meeting the bounds given on the Generalizations and Extensions page. Jiang [Ji] gave a construction for n < 16.

• Given a set system, what is the complexity of determining whether it can be rendered as an Euler diagram? For a non-standard definition of Venn diagram an NP-completeness result is known (Johnson and Pollack [JP]). THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5.