 THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5.  # Venn Diagram Survey Generalizations and Extensions

[ generalizing | symmetric | Euler ]

## 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 cycle9, C, of length 2n, together with a regular 2n-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 π / 2n 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 2n 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 2n regions in any symmetric diagram. Grünbaum gave the lower bound I(n) on the number of required regions:

I(n) = 2 + n (Cn - 2 ),
where Cn is the number of binary necklaces of length n. The numbers Cn 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 2n 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 2n.

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.

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 = { C1, C2, ..., Cn } 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 X1, X2, ..., Xn is connected, where each Xi is either int(Ci ) (the interior of Ci ) or is ext(Ci ) (the exterior of Ci ). 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).

Set system Venn diagram Euler diagram Comments
{Ø,A,B,AB}  {Ø,B,AB}  {Ø,A,B}  {Ø,AB}  This is an iEuler (infinitely intersecting) diagram.
{Ø,B}  {Ø} . THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5.