Hi Martin
On 29/04/2025 18:25, Martin Baker wrote:
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"
The "simple" is puzzling. I know no formula at all that could tell T(n)
for arbitrary n. Do you?
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.
What's the meaning of "efficient"?
https://codegolf.stackexchange.com/questions/2773/calculate-the-number-of-topologies-on-1-2-n
All these codes play out for n<=10, so one should identify the
time/space complexity of the algorithm:
O(1) - Excellent/Best
O(log n) - Good
O(n) - Fair
O(n log n) - Bad
O(n^2), O(2^n) and O(n!) - Horrible/Worst
Some quotations from the link above:
Python (147 chars): Quick for N<=6, slow for N=7, unlikely N>=8 will
ever complete.
Haskell (144 chars. )Extremely slow for n > 4.
So what am I missing here? Why do they say its so difficult?
It seems to be difficult for n > 10 ...
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?
Maybe studying current opinions ...
https://www.researchgate.net/post/Is-there-any-method-to-know-the-number-of-topologies-defined-on-a-set
https://arxiv.org/pdf/1503.08359
https://cs.uwaterloo.ca/journals/JIS/VOL9/Benoumhani/benoumhani11.pdf
One of your links mentions the "Union-Closed Sets Conjecture".
https://dwest.web.illinois.edu/openp/unionclos.html
Although I have no idea how it's connected with this problem, the
associated ideas may be helpful.
BTW, your code works, however, n=6 also hot-smoked my laptop ...
(14) -> l5:=allTopologiesOnSet [1,2,3,4,5] ;
Type: List(TopologyFinite)
Time:
1.90 (EV) + 0.02 (GC) = 1.92 sec
(15) -> #l5
(15) 6942
so we are far from O(n*log n) ...
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/612fb877-afb8-474e-8540-8d252e528847%40gmail.com.
