Chip's Technical Blog

Tech commentary of thoughts, challenges, how-to's, and the mundane.

Archive for August, 2012

Recent work in Venn Diagrams

Monday, August 13th, 2012

As an undergraduate (and for a brief period once I graduated), I worked on areas of discrete math, including Venn diagrams. In fact, I helped develop the constructive proof that rotationally symmetric Venn diagrams existed for all prime numbers of curves [1]. Note that for non-prime numbers of curves, rotationally symmetric Venn diagrams are known to not exist.

However, these diagrams (graphs) are not “simple”. A bit later, I helped Ruskey, Savage, and Weston prove that you could produce “half-simple” rotationally symmetric Venn diagrams for prime numbers of curves [2]. But it has remained unknown whether they could be simple. Today, I read that it has been shown that for 11 curves, they can be simple. See Ruskey’s writeup for pictures [3], or this blog post [4] by Adrian McMenamin for a discussion of what simplicity means and an overview of the technique.

Note that while I made my contributions, Ruskey and Savage are considerably more established in this area. Frank Ruskey is particularly well known for his work in graph algorithms. So when I talk about my part of this research, while I had my contributions, it is of course but one small part of the scientific process. It’s nice to see that this has continued, and to feel like I was part of helping make this happen.

[1] Jerry Griggs, Charles Killian, and Carla Savage. Venn diagrams and symmetric chain decompositions in the Boolean Lattice. Electronic Journal of Combinatorics. Volume 11, January 2, 2004. [http://chip.kcubes.com/research/venn/v11i1r2.pdf] (An article about this result appeared in Science, Vol. 299, January 31, 2003 and it was the subject of a front page article in the January 2004 issue of SIAM News. Additionally, this work was featured in the December 2006 issue of the Notices of the AMS.)

[2] Charles Killian, Frank Ruskey, Carla Savage, and Mark Weston. Half-Simple Symmetric Venn Diagrams. Electronic Journal of Combinatorics. 2004. [http://www.cs.uvic.ca/~ruskey/Publications/HalfSimple/HalfSimple.pdf]

[3] http://webhome.cs.uvic.ca/~ruskey/Publications/Venn11/Venn11.html

[4] http://cartesianproduct.wordpress.com/2012/08/12/venn-diagrams-for-11-sets/

Chip's Technical Blog is proudly powered by WordPress
Entries (RSS) and Comments (RSS).