On Tue, Apr 29, 2025 at 05:25:40PM +0100, 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" 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?
Number of topologies grows very fast with n, any method which tries
to generate all topologies and count them is going to be inpractical
even for moderately large n.
> 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?
1) Use more compact representation of topology than list of sets.
2) Count only T_0 topologies, count only representatives of
homomorphism classes
Wikipedia page that you cited gives formula to compute number of
topologies knowing number of T_0 topologies. T_0 topologies
are in 1 to 1 correspondence with partial orders, so can be represented
in reasonably compact way. If you generate partial orders in
specific way, for example minimal elements first, maximal last
you can limit number of times that you generate the same
isomorphism class of partial order. You can count partial
orders using formula
#P_n = \sum #c_i
#c_i = n!/#S_i
where #c_i is cardinality of isomorphism class i and #S_i is
cardinality of stabilizer of a representative of class i.
Most topologies are likely to have small stabilizers, so the
formulas above are likely to require much less work than
generating all topologies.
--
Waldek Hebisch
--
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/aBYJYwAVf8_5p3DI%40fricas.org.
