Its taken me a long time to work it out but I have written spad code to
generate a list of all topologies on a given finite set.
I worked out an algorithm myself (I didn't try to reverse engineer the
lisp code mentioned in a previous thread which was mostly about
simplicial complexes).
I think the approach I worked out is correct but I don't know how to
check for sure. The results look correct and it produces the correct
number of topologies as you can see here:
(1) -> #allTopologiesOnSet [1,2,3]
(1) 29
Type:
PositiveInteger
(2) -> #allTopologiesOnSet [1,2,3,4]
(2) 355
Type:
PositiveInteger
(3) -> #allTopologiesOnSet [1,2,3,4,5]
(3) 6942
Type:
PositiveInteger
(4) -> #allTopologiesOnSet [1,2,3,4,5,6]
(in this case a thread ran 100% for 4 hours until I gave up and pressed ^C)
These results agree with the table at the bottom of the Wiki page here:
https://en.wikipedia.org/wiki/Finite_topological_space
My code is here:
https://github.com/martinbaker/fricasAlgTop/blob/topology/topology.spad
This Wiki page says "There is no known simple formula to compute T(n)
for arbitrary n" and forums like this:
https://mathoverflow.net/questions/8970/number-of-valid-topologies-on-a-finite-set-of-n-elements
seem to suggest that an efficient algorithm is an open problem.
So what am I missing here? Why do they say its so difficult?
The code seems to be efficient (Of course my spad code can be improved
but I cant see how the underlying algorithm could be made more
efficient). It doesn't generate a lattice of latices and then filter out
valid topologies, instead it recurses directly to the required topologies.
So if we had a lattice of latices (with the top and bottom elements
removed as they all have top and bottom elements) we would need to check
2^(2^n-2)-2
potential topologies.
But my code grades the power set and then takes the power set of each
grade separately (which is a lot less) and it does not recurse to the
next grade for cases where the required meets and joins don't exist so
it cuts out the invalid cases at an early stage.
Any ideas how I could check this out further?
Martin
--
You received this message because you are subscribed to the Google Groups "FriCAS -
computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To view this discussion visit
https://groups.google.com/d/msgid/fricas-devel/10135461-c306-46ee-8951-e570aa7a62ab%40martinb.com.
