A few things about the images in my previous post that you may or may not have noticed:
- As several commenters figured out, the th diagram (starting with ) is showing every possible subset a set of items. Two subsets are connected by an edge when they differ by exactly one element.
- All subsets with the same number of elements are aligned horizontally.
- Each diagram is made of two copies of the previous diagram—one verbatim, and one with a new extra element added to every subset, with edges connecting corresponding subsets in the two copies. Do you see why this makes sense? (Hint: if we want to list all subsets of a set, we can pick a particular element and break them into two groups, one consisting of subsets which contain that element and one consisting of subsets which don’t.)
- As commenter Denis pointed out, each diagram is a hypercube: the first one is a line (a 1-dimensional “cube”), the second is a square, the third is a cube, then a 4D hypercube, and so on. (On my own computer I rendered them up to but it gets very hard to see what’s going on after .)
- Each subset can also be seen as corresponding to a bitstring specifying which elements are in the set. A dot corresponds to a 1, and an empty slot to a 0. So another way to think of this is the graph of all bitstrings of length , where two bitstrings are connected by an edge if they differ in exactly one bit.
- Thinking of it as bitstrings makes it clearer why we get hypercubes: each bit corresponds to a dimension. So for example for the 3D case you could think of the three bits as corresponding to back/front, left/right, and down/up.
- I drew something similar to this many years ago, in Post without words #2. The big difference is that it recently occurred to me how to lay out the nodes recursively to highlight the hypercube structure, so they don’t all just smoosh together on each line.
- There was actually some interesting math involved in figuring out the horizontal offsets to use for the subset nodes; perhaps I’ll write about that in another post!
The bigger diagrams get really wide. Would it help to draw the individual subsets in a vertical bar instead of a horizontal one? I’d love to see one more level!
Good idea! See PWW #31.
It’s a Hasse diagram!
Good point! I was going to mention that but forgot. =)