Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
4  
What do you mean by 'valid'? There are lots of references at research.att.com/~njas/sequences/A000798, and in the related sequences. –  Mariano Suárez-Alvarez Dec 15 '09 at 9:15
    
Presumably a subset of the power set which is not closed under either union or intersection. –  Ryan Budney Dec 15 '09 at 9:16
1  
Well, thanks for the reference. Also, by a valid topology, I mean subsets of the power set that define a topology. I guess it was redundant. –  Harry Gindi Dec 15 '09 at 9:19
    
It appears to be open (so you should probably add that tag), but I too am curious about why it appears to be intractable. –  Jonas Meyer Dec 15 '09 at 9:44

5 Answers 5

up vote 17 down vote accepted

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?

share|improve this answer
    
Oh, right! I meant to add that if you just want loose asymptotics, that's doable. There's a paper of Kleitman and Rothschild which is listed as a reference in OEIS. It doesn't seem to be online (it's kind of ancient), but I seem to recall skimming it once, and it looked... pleasurable. –  Harrison Brown Dec 15 '09 at 12:06
1  
Awesome answer, by the way. The apology is gratuitous. –  Jonas Meyer Feb 21 '10 at 6:39

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.

share|improve this answer
1  
Two comments. The short one first, since the long one is gonna be looong. Perfect matchings are usually enumerated by computing a permanent, not a determinant. Permanents are, like Qiaochu said, crazy useful; actually, computing the permanent of a matrix is #P-complete, where #P is a class of counting problems roughly analogous to NP (but considerably bigger and badder -- see e.g. Toda's theorem). –  Harrison Brown Dec 15 '09 at 17:25
    
Sets with a G action can be thought of as a particular kind of groupoid. It turns out that occasionally, for Burnside/Polya type results, you just need this groupoid structure plus some ad-hoc, group-action-like properties. In particular it can be fruitful to think about setoids, i.e. sets with equivalence relation. And there is a (straightforward!) characterization of topologies on [n] as the quotient of an easy-to-enumerate set by a certain equivalence relation. Which set and which relation is left as an exercise; unfortunately the one I'm thinking of doesn't have nice enough properties. –  Harrison Brown Dec 15 '09 at 17:38
    
Right, but for planar graphs one can get away with the Pfaffian. The reason to prefer determinants for exact enumeration is that there are a lot of ways to evaluate determinants - one of the cleanest, for example, is if the matrix has enough structure that one can write down its eigenvalues explicitly. –  Qiaochu Yuan Dec 15 '09 at 18:18
    
Okay, for planar graphs sure, but not in general. Absolutely, determinants are considerably more natural. Actually, is the permanent even constant on conjugacy classes? Probably, but not for as obvious reasons as the determinant. –  Harrison Brown Dec 15 '09 at 18:35
1  
If the permanent were constant on conjugacy classes then it would be equal to the determinant. (Note that the two coincide for diagonal matrices.) –  Qiaochu Yuan Dec 15 '09 at 18:38

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$.

share|improve this answer

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.

share|improve this answer
    
The correct link is now oeis.org/A000798 –  Ross Millikan Jan 10 at 2:38

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

share|improve this answer
4  
As much as I love that conjecture (well, okay, love/hate), I also don't see how it relates to a question about enumeration. Elaboration? –  Harrison Brown Dec 15 '09 at 11:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.