THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5. |
This page gives some examples of k-fold Venn diagrams with various symmetries.
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.
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^{9}, C, of length 2^{n}, together with a regular 2^{n}-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^{n} 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.
It is natural to consider diagrams that are "close" to Venn diagrams, in that the number of regions is as close to 2^{n} 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^{n} regions in any symmetric diagram.
Grünbaum gave the lower bound I(n) on the number of
required regions:
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^{n} | 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^{n}.
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 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_{1}, C_{2}, ..., 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_{1}, X_{2}, ..., 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.
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. |