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?
$\begingroup$
$\endgroup$
5
-
6$\begingroup$ What do you mean by 'valid'? There are lots of references at research.att.com/~njas/sequences/A000798, and in the related sequences. $\endgroup$– Mariano Suárez-ÁlvarezCommented Dec 15, 2009 at 9:15
-
$\begingroup$ Presumably a subset of the power set which is not closed under either union or intersection. $\endgroup$– Ryan BudneyCommented Dec 15, 2009 at 9:16
-
2$\begingroup$ 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. $\endgroup$– Harry GindiCommented Dec 15, 2009 at 9:19
-
1$\begingroup$ It appears to be open (so you should probably add that tag), but I too am curious about why it appears to be intractable. $\endgroup$– Jonas MeyerCommented Dec 15, 2009 at 9:44
-
$\begingroup$ See also this paper, arxiv.org/pdf/1503.08359.pdf $\endgroup$– OurCommented Oct 2, 2018 at 5:52
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
3
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:
- 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.
- 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.
- 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?
answered Dec 15, 2009 at 11:34
-
1$\begingroup$ 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. $\endgroup$ Commented Dec 15, 2009 at 12:06
-
4$\begingroup$ Awesome answer, by the way. The apology is gratuitous. $\endgroup$ Commented Feb 21, 2010 at 6:39
-
$\begingroup$ "given a description of a structure type and 𝑛, count the number of structures on an n-element set" : Recently people in AI figured out how to count the number of structures consistent with a formula in First Order Logic with two variables, does this have any impact on combinatorics ? arxiv.org/abs/1412.1505 $\endgroup$– SagarMCommented Nov 11, 2020 at 17:10
$\begingroup$
$\endgroup$
1
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$.
answered Dec 15, 2009 at 15:26
-
4$\begingroup$ Kleitman and Rothschild later vastly improved their result by giving an asymptotic formula (not just log-asymptotic) in Trans. AMS 205 (1975), 205--220. $\endgroup$ Commented Apr 10, 2020 at 20:21
$\begingroup$
$\endgroup$
5
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.
answered Dec 15, 2009 at 15:16
-
1$\begingroup$ 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). $\endgroup$ Commented Dec 15, 2009 at 17:25
-
$\begingroup$ 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. $\endgroup$ Commented Dec 15, 2009 at 17:38
-
$\begingroup$ 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. $\endgroup$ Commented Dec 15, 2009 at 18:18
-
$\begingroup$ 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. $\endgroup$ Commented Dec 15, 2009 at 18:35
-
3$\begingroup$ If the permanent were constant on conjugacy classes then it would be equal to the determinant. (Note that the two coincide for diagonal matrices.) $\endgroup$ Commented Dec 15, 2009 at 18:38
$\begingroup$
$\endgroup$
0
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.
answered Dec 15, 2009 at 11:18
$\begingroup$
$\endgroup$
You can find the latest results here: https://arxiv.org/pdf/1503.08359.pdf
$\begingroup$
$\endgroup$
1
This question is closely related to the Union-Closed Sets Conjecture which is an open question proposed in 1979.
answered Dec 15, 2009 at 11:01
-
10$\begingroup$ 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? $\endgroup$ Commented Dec 15, 2009 at 11:54