More fun with symmetric Venn diagrams
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Mark Weston,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
Many researchers have had fun searching for and rendering
symmetric Venn diagrams, culminating in the recent result of
Griggs, Killian and Savage (Electronic Journal of Combinatorics,
"Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice",
11 (2004) R2),
that symmetric Venn diagrams on n curves exist
if and only if n is prime.
Our purpose here is to point out ways to prolong the fun by
introducing and finding the basic properties of
Venn and nearVenn diagrams that satisfy relaxed notions of symmetry,
while leaving tantalizing open problems.
A symmetric Venn diagram is one that possesses a rotational symmetry
in the plane.
A monochrome symmetric Venn diagram is one that is
rotationally symmetric when the colours of the curves are ignored.
A necessary condition for the existence of a monochrome
simple Venn diagram is that the number of curves be a prime power.
We specify conditions under which all curves must be noncongruent and
give examples of small visuallystriking monochrome symmetric Venn diagrams
found by algorithmic searches. A Venn diagram partitions the plane into
2^{n} open regions. For nonprime n
we also consider symmetric diagrams where the number
of regions is as close to 2^{n} as possible, both larger and smaller.

Appears in FUN 2004, Third International Conference on
FUN with Algorithms,
Isola d'Elba, Italy, proceedings by Edizioni PLUS 
Università di Pisa, pp. 235246 (ISBN 8884921503).

One of seven papers selected for submission to a special issue of
Theory
of Computing Systems, 39 (2006) 413423.
(Appeared Electronically July 13, 2005
DOI: 10.1007/s0022400512431).

The postscript file (colour figures)
is 1.45mb.

The pdf file (colour figures) is 757kb.

The TCS version is has grayscale figures.

Comments:

It would have been better if the value of M'(n) was defined to be
2 + n L(n), where L(n)
is the number of Lyndon words of length n. This gives better bounds.

Conjecture 2 should have the condition N > 4, since there is
a simple Euler diagram with 4 curves and 14 regions.
Back to list of publications.