[3-circle Venn diagram -- click me for main page]

THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5.

Venn Diagram Survey
Generalizations and Extensions

Generalizing Venn Diagrams

We began the "What is a Venn diagram page" with a generalization, namely, the independent family, and there are several other variants that have appeared in the literature. Perhaps the most important generalization, Euler diagrams, we treat in a separate section below.

k-fold Venn diagrams

In an ordinary Venn diagram each intersection consists of one connected region. Fisher, Koh, and Grünbaum [FGK] define a k-fold Venn diagram to be one in which each intersection consists of exactly k connected regions. They show how to construct such diagrams for any n,k > 1.

This page gives some examples of k-fold Venn diagrams with various symmetries.

d-dimensional Venn diagrams

Independent sets and Venn diagrams can be generalized to more than two dimensions. In the definition of independent set and Venn diagram, "curve" gets replaced with "boundary of an open d-cell" (that is, homeomorphic to a d-sphere) and "region" is replace with "open d-cell". Rényi, Rényi, and Surányi [RRS] proved that an independent family of d-spheres has at most d+1 members, thereby generalizing the result that a Venn diagram whose curves are circles contains at most three curves.

Grünbaum [Gr75] mentions several general geometric problems regarding d-dimensional diagrams where the sets are required to be boundaries of d-polytopes or convex regions.

Infinitely intersecting Venn diagrams

If we relax the restriction that Venn diagrams meet in only finitely many points, then we lose some of the nice graph theoretic considerations (e.g., the dual graph is no longer a subgraph of the hypercube), but do gain some flexibility. Below we show a diagram made from three congruent curves, red, blue, and green. Each curve is congruent and they are successively rotated by π/4 radians about the central point.

Such a construction is possible for any n, and is attributed to Peter Shor in Knuth, Graham, and Patashnik [GKP]. The idea of the construction is to take a De Bruijn cycle⁹, C, of length 2ⁿ, together with a regular 2ⁿ-gon inscribed in a circle. Make a curve by successively choosing a circular arc for each 1 in C and a polygonal edge segment for each 0. To obtain the other curves rotate this one about the central point by 2 k π / 2ⁿ radians for k = 1,2,...,n-1. The example shown above is created by starting with the De Bruijn cycle C = 00011101.

We have already seen some other infinitely intersecting diagrams; the Venn polyominoes found in the section on area-proportional diagrams also have infinitely intersecting edges.

Generalizations of Symmetric Diagrams

On the page Variants on Symmetry we have already discussed a generalization of symmetric Venn diagrams, namely pseudo-symmetric diagrams (which retain the property of being a Venn diagram while relaxing the notion of symmetry). Here we take the opposite tack by retaining the strict definition of symmetry but extending it to non-Venn diagrams. Our motivation is the fact that if n is not prime, symmetric Venn diagrams cannot exist.

It is natural to consider diagrams that are "close" to Venn diagrams, in that the number of regions is as close to 2ⁿ as possible while still being symmetric. We have already seen on the "What is Venn Diagram?" page that Venn diagrams are instances of independent families, and in [Gr99], Grünbaum generalized the concept of symmetry in Venn diagrams to independent families.

If n is not prime, there will be some i such that regions enclosed by i curves must be repeated to create a symmetric diagram, and thus we must have more than 2ⁿ regions in any symmetric diagram. Grünbaum gave the lower bound I(n) on the number of required regions:

I(n) = 2 + n (C_n - 2 ), where C_n is the number of binary necklaces of length n. The numbers C_n are well-studied, see [GKP, pp. 139-141] for explicit formulae and further references; also see the page Symmetric Diagrams, Necklaces, and Chains for some important connections between necklaces and constructing symmetric Venn diagrams. The table below gives I(n) for small non-prime values of n.

The figure to the left, from [Gr99], shows a symmetric independent family of four equilateral triangles with I(4) = 18 regions.

In the same paper Grünbaum conjectured that symmetric independent families with only I(n) regions exist for every integer n (this includes the special case that n is prime, and the symmetric independent family is just a symmetric Venn diagram - it has no repeated regions).

We can also create a symmetric diagram by removing as few regions as possible from a Venn diagram to create an Euler diagram that is not an independent family (as some regions will be missing) but will retain rotational symmetry - we can call these near-Venn diagrams. Symmetric near-Venn diagrams for non-prime n are maximally symmetric Euler diagrams in the sense that they cannot have any more regions added without either losing their symmetry or repeating regions. The numbers E(n) in the table below are the upper bounds on the number of regions in a symmetric near-Venn diagram (they are not difficult to calculate; see [RW] for a formula).

n	E(n): upper bound on regions in symmetric near-Venn diagram	2ⁿ	I(n): lower bound on regions in symmetric independent family
4	14	16	18
6	56	64	74
8	242	256	274
9	506	512	524
10	1012	1024	1062
12	4070	4096	4202

As we can see, the numbers I(n) and E(n) closely bracket 2ⁿ.

In [Ji], Zongliang Jiang extended the construction algorithm of [GKS] for prime n to composite n < 16; this construction repeats the minimum number of regions possible to create symmetric independent families with I(n) regions.

A symmetric independent family of 6 curves. The repeated regions are labelled, for example the region enclosed by the black, red and green curves is labelled by a "4" and occurs three times.
A symmetric independent family of 8 curves that is drawn to be near-simple, that is, as close to simple as possible: there are only 16 points where more than 2 curves intersect.
A near-Venn diagram of 6 curves, drawn to be near-simple.

In addition to examples for small n in [Gr99], many examples of larger symmetric independent families and near-Venn diagrams can be found in [RW], [Wes], and [Ji]. The above examples are from [Wes].

Grünbaum also noticed, as have we, that, asides from the case E(4) = 14, for which a simple diagram can be easily constructed, there do not seem to be any simple symmetric independent families or near-Venn diagrams attaining the given bounds. Why this should be is entirely unknown!

Euler Diagrams

Euler diagrams predate Venn diagrams, but are distinct. They were introduced by Euler to aid in the understanding of syllogisms. In that context they have certain deficiencies, some of which Venn tried to rectify with Venn diagrams.

Our formal working definition of an Euler diagram is found below. Let C = { C₁, C₂, ..., C_n } be a collection of finitely intersecting simple closed curves drawn in the plane. The collection C is said to be an Euler diagram if the intersection of X₁, X₂, ..., X_n is connected, where each X_i is either int(C_i ) (the interior of C_i ) or is ext(C_i ) (the exterior of C_i ). If infinite intersections are allowed we refer to the diagrams as iEuler diagrams.

In other words, an Euler diagram is like a Venn diagram except that intersections of curve interiors are allowed to be empty. From this point of view a Venn diagram is a particular type of Euler diagram. As used in the analysis of syllogisms, each region of a Venn diagram is shaded (in red in the table below) according to whether the region can contain any members. In this way any set system can be represented by a Venn diagram. In an Euler diagram a region is present if and only if it contains at least one member; there is no shading. As a consequence not all set systems may be represented by Euler diagrams; for example the reader can verify that the system { ∅, A, B, AC, BC } cannot be drawn.

Euler wrote four letters in February of 1761 which contain Euler diagrams as defined above (from the Brewster translation) [Eu].

LETTER CII. Of the Perfections of a Language. Judgements and Nature of Propositions, affirmative and negative; universal or particular.
LETTER CIII. Of Syllogisms, and their different Forms, when the first Proposition is universal.
LETTER CIV. Different Forms of Syllogisms, whose first Proposition is particular.
LETTER CV. Analysis of some Syllogisms.

Euler always drew his diagrams as collections of circles, but remarks in Letter CIII, These circles, or rather these spaces, for it is of no importance of what figure they are of,.... We know of no written record that Euler ever made use of the familiar 3 circle Venn diagram.

Chapter V of John Venn's book Symbolic Logic contains an explanation and comparison of Venn and Euler diagrams [Ve81]. The second part of his historical notes contains much information about the history of diagrammic reasoning.

Since Venn's time, his diagrams have since been extended to Venn-Pierce diagrams, which add extra information in the form of symbols inside the regions to enable them to be used as valid logical proof mechanisms. The book by Sun-Joo Shin [Sh] contains a clear discussion of the differences between Euler, Venn, and Pierce diagrams, and a proof that with some enhancements the Venn system provides a sound and complete logical representation system.

Comparison

In the table below we show the corresponding set system, Venn diagram, and Euler diagram for 2-sets. Up to a relabelling of sets, all possibilities are shown (subject to the constraint that they include the empty set).