I love binary trees

A few years ago I was very proud of myself for managing to translate the original Pascal of the Reingold-Tilford algorithm into C/C++ and every since then I have had a fascination for drawing binary trees.

NoC with binary memory tree


The one drawn here was actually done “by hand” in Metapost – I realised only as I finished it that I could have or maybe should used an algorithmic approach and not a heuristic (“does it look ok?”), though Metapost is a pretty inflexible programming tool (though as this book shows can produce some beautiful results) and I reckon a decent tree drawing algorithm in that ought to be worth at least an MSc.

Graph cartesian products

On the basis that knowing some more about Graph Theory won’t do me any harm when thinking about operating system behaviour, I am reading about that too right now.

But I found the book’s explanation of a Graph Cartesian Product rather less than full, so here is my attempt to make it a bit clearer.

Say we have graph G_1 with vertices (v_1, v_2, v_3) and graph G_2 with vertices (w_1, w_2, w_3, w_4) , then our cartesian product graph is G_3 with vertices ((v_1, w_1), (v_1, w_2), (v1, w_3), (v_2, w_4),(v_2, w_1), (v_2, w_2), (v2, w_3), (v_2, w_4),(v_3, w_1), (v_3, w_2), (v3, w_3), (v_3, w_4))

Which vertices in this new graph are adjacent?

The vertices are adjacent if – and only if – taking the new vertices to be of the form (v_n, w_n) (v^{\prime}_n, w^{\prime}_n) – if v_n = v^{\prime}_n and w_n is adjacent to w^{\prime}_n in G_2 OR w_n = w^{\prime}_n and v_n is adjacent to v^{\prime}_n in G_1.

Venn diagrams for 11 sets

Ask most people about set theory and you will get a blank look, but ask them about a Venn diagram and they are much more likely to understand: indeed Venn diagrams are so well grasped that Mitt Romney’s campaign for the US Presidency recently attempted to make use of them (though I am not sure it was much of a success, but that’s another story…)

So called 2-Venn (two circles) and 3-Venn diagrams are very familiar. But higher dimension Venn diagrams that are (relatively) easy to grasp (I’ll explain what I mean by that below) are actually difficult to produce – and until last month nobody had managed to get beyond 7.

3-Venn diagram

So, let’s state a few basic properties of any Venn diagram (here is a good general survey of Venn diagrams)- firstly – each region (face) is unique – there is only one region where the bottom curve intersects with the right curve alone, and only one where it intersects with the left curve alone and only one where all three curves intersect (the grey region) and so on.

This image (taken from that survey, apologies) – shows a series of set intersections which are not a Venn diagram:

Not a Venn diagramFor instance, we can see the two shaded areas both represent intersections of the ‘blue’ and ‘red’ sets.

A second point is that there is a finite number of intersections. In other words segments of curves cannot lie on top of one another (in fact this rule means the intersections must be in the form of Eulerian points of zero length – as, following on from the last post about Aristotle’s Wheel Paradox, any segment of a curve is continuous and has an uncountable infinite number of points).
The 3-Venn example above illustrates some of the key points about easier to understand Venn diagrams – firstly it is simple: no intersection is of more than two curves and secondly it is symmetric. In fact, if we are willing to ignore these points we can draw Venn diagrams of any number of sets, each with less intelligibility than the last.

Drawing higher number simple and symmetric Venn diagrams is exceptionally difficult and it has been proved that such n-Venn diagrams only exist when n is a prime.

So we have 2-Venns and 3-Venns, and mathematicians have managed 5-Venns:Simple, symetric 5-Venn from Journal of CombinatronicsAnd 7-Venns:

Simple, symmetric 7-Venn from Journal of Combinatronics

But, until now, simple symmetric 11-Venns have been elusive. Certainly 11-Venn’s have been around – as the example below shows:

Symmetric, non-simple 11-Venn from Journal of CombinatronicsThis example is symmetric but it is not simple.

Now, though, a breakthrough has been made. Named newroz – the Kurdish name for the new year – the first simple, symmetric 11-Venn has come from Khalegh Mamakani and Frank Ruskey, both of the Department of Computer Science at the University of Victoria, Canada.

And it is beautiful:

11-Venn from Khalegh Mamakani, Department of Computer Science, University of Victoria, Canada. Frank Ruskey, Department of Computer Science, University of Victoria, Canada. That said, I don’t think it will be featuring in any presidential campaigns just yet – by definition there are 2^{11} - 1= 2047 intersecting regions, probably a bit more than even the keenest voter would care for.