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".