Question

I've heard that the problem of counting topologies is hard, but I couldn't really find anything about it on the rest of the internet. Has this problem been solved? If not, is there some feature that makes it pretty much intractable?

Answer 1

It's wiiiiiiide open to compute it exactly. As far as I know the "feature that makes it intractable" is that there's no real feature that makes it tractable. Very broadly speaking, if you want to count the ways that a generic type of structure can be put on an n-element set, there's no efficient way to do this -- you basically have to enumerate the structures one by one. This is essentially because "given a description of a structure type and $n$, count the number of structures on an n-element set" is a ridiculously broad problem which ends up reducing to lots and lots of different counting and decision problems. Alternatively I think you can argue via Kolmogorov complexity and all that, but that's not my style?

So in any case, the burden of proof is on the person who claims that an efficient counting algorithm should exist. (If you believe some crazy things about complexity theory, like P = PSPACE, this starts to become less true since the structure types hard to enumerate will usually be hard to describe. But if you believe that you're a lost cause in any case :P) It's still reasonable to ask for further justification, though. I'd attempt to give some, but I've been awake for like 30 hours and it would be even more handwavey than the above. The short version: If you do enough enumerative combinatorics, you start to see that nice formulas for enumerating structures arise from one of a few situations. Some really big ones are:

1. The ability to derive a sufficiently nice recurrence relation. This is a rather nebulous property, and some surprising structure types have cute recurrence relations. I can't really tell you a good solid reason why the number of finite topologies doesn't admit a nice recurrence relation; if you work with it a while, it just doesn't feel like it does.
2. A classification theorem such that the structures in each class have nice formulas. Sometimes these are deep, sometimes they aren't. One non-deep example is in the usual (non-linear-algebra) proof of Cayley's formula on the number of trees. Point-set topology is weird, and it's pretty weird even in the finite case. This is out of the question.
3. If the set of structures on a set of n elements is very rigid, there may be an "algebraic" way of counting them. Again, point-set topology is too weird for this to kick in.

So my answer boils down to: It's intractable 'cause it is. Not a particularly satisfying reason, but sometimes that's the way combinatorics works. Sorry if you read that whole post -- I meant for it to be shorter and have more content, but it ended up like most tales told by idiots. But hopefully you learned something, or at least had fun with it?

Answer 2

I'll expand a little on Harrison's answer. There are several techniques in algebraic combinatorics that allow for exact enumeration of unordered structures; they include

• Writing down the generating function in terms of elementary functions. This usually requires that your structure have something to do with the structure $e^x$ of sets, the structure $\frac{1}{1 - x}$ of linear orders, or related structures. Important ways to combine structures include sum, product, composition, and derivative, all of which have known combinatorial meanings. But, on the surface, there appears to be no way to encode the structure of a topology in this way.

• Writing down a functional equation the generating function satisfies. This is most useful with tree-like structures, since the recursive nature of their definition is reflected in certain functional equations. For example, the generating function $f$ of labeled trees famously satisfies $f = xe^f$, and together with Lagrange inversion we easily obtain Cayley's formula. But topologies don't seem to be a tree-like structure in any obvious way.

• Exhibiting the sequence as the evaluation of a sequence of determinants. This is an incredibly useful technique; it can count tableaux and perfect matchings and all sorts of crazy things, but problems to which this technique applies have a certain feel to them and this one doesn't even come close to fitting the bill.

• Using some variant of Burnside's lemma or Polya's theorem. But there seems to be no useful way to interpret finite topologies in terms of a group action.

Since finite topologies are an algebraic structure of sorts - a set closed under two operations - you might like to think about a correspondingly difficult algebraic problem, which is the enumeration of finite groups.

Answer 3

The best result I know is found in the article The number of finite topologies, by D. Kleitman and B. Rothschild, where they state that the base-2 logarithm of the number of distinct topologies on a set of $n$ elements is asymptotic to $n^2/4$.

Answer 4

Sloane's encyclopedia gives some references. I think that if something moves in this question, then Sloane's site will be one of the first to be updated...

I am not sure in how far this has to do the Union-Closed Sets Conjecture - the latter is just an extremal-combinatorics style assertion. I don't see how to use it for an enumeration.

Answer 5

This question is closely related to the Union-Closed Sets Conjecture which is an open question proposed in 1979.