A few words about PWW #30

A few things about the images in my previous post that you may or may not have noticed:

  • As several commenters figured out, the nth diagram (starting with n = 1) is showing every possible subset a set of n 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 n=8 but it gets very hard to see what’s going on after 5.)
  • 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 n, 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!

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in posts without words and tagged , , , , , , , . Bookmark the permalink.

4 Responses to A few words about PWW #30

  1. 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!

  2. Riley says:

    It’s a Hasse diagram!

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.