Counting Connections

A couple of weeks ago I began a course at work on computational topology.  The introduction included the definition of a topological space, which, briefly, is a set X and a collection of subsets of X that includes the empty set and the set X itself, and is closed under (arbitrary) unions and (finite) intersections.  To illustrate the idea, the instructor used the simple example of a set X with just 3 points.  He presented the class with 11 different examples of collections of subsets of X, and asked us to identify which collections were topological spaces and which did not satisfy the closure properties above.  (See here for a graphical view of similar examples.)

I have a bad habit of always trying to count things.  Forget about the topology connection for a moment; since 11 seemed like a strange, rather specific number, it occurred to me to wonder whether this made up all possible collections of subsets, or if not, how many more are there?  Answering these questions involves some interesting mathematics, including what I suppose is my favorite theorem of all, if I were ever pressed to pick one.

First, we must be precise about what we are counting.  Given a set X with n elements, how many different collections of subsets of X are there?  It depends on what we mean by “different.”  There are 2^{2^n} distinct collections of subsets, but this counting assumes, for example, that the collection {{}, {a}, {a,b,c}} is distinct from the collection {{}, {b}, {a,b,c}}, when for our purposes we don’t really care about the distinction between a and b.

What we want, then, is to group collections of subsets together under a suitable equivalence relation, and count equivalence classes.  This gets tricky, because the equivalence classes do not all have the same size.  Fortunately, there are some very powerful tools available, including the Orbit-Stabilizer Theorem, Burnside’s Lemma (actually due to Frobenius), and Polya’s Theorem, all of which are applications of the very useful idea of group action on a set.

I won’t bother with the rather tedious calculations here.  The punch line is that there are not just 11 but 20 different collections of subsets.  However, a separate calculation yields that exactly 9 of these collections correspond to topological spaces, so it turns out that the instructor’s original examples included all of these, with just a couple of “failures” thrown in.

Finally, as a result of this exercise, I learned about another interesting application of this same counting problem to switching theory.  Computing the first few terms of the sequence of numbers of collections of subsets of n elements, and checking the Online Encyclopedia of Integer Sequences, we find sequence A003180, which also counts the number of Boolean functions of n variables, unique up to permutation of the inputs.  In hindsight, this makes sense; we can represent particular input values to a Boolean function as the subset of inputs that are true (or 1), and characterize a particular Boolean function by the collection of (subsets of) inputs for which the output is true (or 1).

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s