From: strauch@emmy.mathematik.uni-dortmund.de (Michael Strauch)
Newsgroups: sci.math,sci.math.symbolic,sci.math.research
Subject: Re: WANTED: algorithm to produce all finite topologies
Date: 9 Feb 1994 16:43:23 GMT
gerstner@mathematik.tu-muenchen.de (Manfred Gerstner) writes:
>I'm sorry to bring up this topic again. But nevertheless I need an efficient
>algorithm to print out all topologies.
>I think of entering a *small* number n and receiving a list of sequences
>of subsets of X := {1,2,...,n}; every sequence being a topology of X.
>(or equivalently: being a base of that topology). It would be fine, if
>each topology comes up exactly once - or even better, only one representant
>up to homeomorphism.
>By "efficient" I mean that I can wait for the result.
>References or ideas for this algorithm are welcome
> - or a list for n = 1 to, say, 7 or 8.
Look at "New Results from an Algorithm for Counting Posets" from J. C.
Culberson and G. J. E. Rawlins, published in Order 7 (90/91), no 4, p 361-374.
There you will find a detailed description for an algorithm for counting
and generating all unlabled finite posets (or non-homeomorphic finite
topologies), which is efficient enough for computing all cases n <= 11.
M. Erne and K. Stege did use the results from this article to compute the
number of labled topologies for n<=14. You will find their work in
"Counting Finite Posets and Topologies", Order 8 (91), p 247-265.
- Michael Strauch -
strauch@emmy.mathematik.uni-dortmund.de
==============================================================================
From: hogan@cs.colorado.edu (HOGAN APOLLO FRANCI)
Newsgroups: sci.math
Subject: Re: finite topological spaces
Date: 17 Apr 1995 18:54:45 GMT
In article <3mstl7$1jgj@tequesta.gate.net>,
Theodore Hwa wrote:
>The following question has occurred to me. Let P(S) denote the power set
>of the set S. Then for a given positive integer n, how many of the
>elements of P(P({1,2,...,n})) are topologies on the set {1,2,..,n}?
>
> Any further suggestions on this problem?
I am currently reading a book "Fundamentals of Pattern Recognition" by
Monique Pavel which describes exactly what you're talking about:
the finite topologies. She refers to Krishnamurthy, V. "On the
number of topologies on a finite set" Amer. Math. Monthly, Vol. 73
(1966), pp. 154-157. And mentions that yes, f(1)=1, f(2)=4 and that
a bound for f(n) is 2^(n*(n-1))-1. Krishnamurthy also "proved that
f(n) is precisely the number of certain nxn matrices of 0's and 1's
with a_ii=1 for all i and with the following property:
For every ordered pair (R_i,R_j), i,j=1,2,...,n, of rows of
(a_ij) and for every index k, a_ji=1=a_ik implies a_jk=1."
(Pavel, 17)
She also points out another reference, J.W.Evans, F.Harary,
and M.S.Lynn: "On the computer enumeration of finite topologies,"
Comm. A.C.M.,Vol.10 (1967), pp.295-313.
Good luck!
--Apollo
GCS/M/O -d+ p--- c++() l u++ e+ m++ s n++ h(--) f-(+) !g w+ t r- y+(*)
--
--Apollo
GCS/M/O -d+ p--- c++() l u++ e+ m++ s n++ h(--) f-(+) !g w+ t r- y+(*)
==============================================================================
From: karner@aut.alcatel.at (Georg Karner)
Newsgroups: sci.math
Subject: Re: Number of topologies
Date: 8 May 1995 08:35:13 GMT
The topic has been discussed on this newsgroup some time ago.
>>> From sieda@hrz.uni-bielefeld.de ( Torsten Sillke) Sep 30 1993
TOP: finite Topologies, finite Posets (T0 Topologies)
TOP- Posets : 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, 2567284,
TOP 46749427, 1104891746, 33823827452, ... Sloane 588
TOP- Topologies: 1, 3, 9, 33, 139, 718, 4535, ... Sloane 1133
TOP- Posets (labeled) : 1, 3, 19, 219, 4231, 130023, 6129859,
TOP 431723379, ...
TOP- Topologies (labeled): 1, 4, 29, 355, 6942, 209527, 9535341,
TOP 642779354, 63260289423, ...
TOP- N. J. A. Sloane, A Handbook of Integer Sequences, p14-16
TOP posets (labeled): ser. 588 (1244)
TOP topologies (labeled): ser. 1133 (1476)
TOP connected topologies (labeled): ser. 648 (1245)
TOP- M Erne, On the cardinalities of finite topologies and the number of
TOP antichains in partially ordered sets, Disc Math 35 (1981) 119-133
TOP table of labeled posets 1..8
>>> From: eclark@gauss.math.usf.edu (Edwin Clark) Feb 14 1994
There is a recent article "The numbers of finite lattices and
finite topologies" by Yasunori Koda (ykoda@rst.fujixerox.co.jp)
in the January 1994 issue of the Bulletin of the Institute of Combinatorics and its applications (subscriptions only $35/year!). He gives the number
of topologies on up to 9 element sets. For up to 7 element sets
see Sloane's "A handbook of integer sequences".