From: bumby@lunar.rutgers.edu (Richard Bumby)
Newsgroups: sci.math.research
Subject: Re: How Many Topologies on a Finite Set?
Date: 2 Jun 1997 17:28:25 -0400
Thomas Haeberlen writes:
>How many topologies (up to homeomorphism) can be defined on a finite set
>with n elements?
>Can anyone give me a good reference to the answer for that question?
>............................
The standard reference is:
J. W. Evans, F. Harary and M. S. Lynn; On the computer enumeration of
finite topologies; Comm. Assoc. Computing Mach. 10 (1967), 295--298.
There should be an update to this enumerative work somewhere, but I
haven't heard of it. I have this reference handy because I
contributed to a paper on the structure of the lattice of topologies.
That paper is:
R. Bumby, R. Fisher, H. Levinson and R. Silverman; Topologies on
Finite Sets; Proc. 9th S-E Conf. Combinatorics, Graph Theory, and
Computing (1978), 163--170
The authorship graph of this paper was a star with Hank Levinson at
the center. He continued working on this question, and I think there
is another paper with a proper subset of the same authors a few years
later in the same conference proceedings. This conference is also the
natural place to look for announcements of new results on the
question.
--
R. T. Bumby ** Rutgers Math || Amer. Math. Monthly Problems Editor 1992--1996
bumby@math.rutgers.edu ||
bumby@dimacs.rutgers.edu || Phone: [USA] 908 445 0277 * FAX 908 445 5530
==============================================================================
From: prenteln@wiley.csusb.edu (Paul Renteln)
Newsgroups: sci.math.research
Subject: Re: How Many Topologies on a Finite Set?
Date: 3 Jun 1997 05:27:09 GMT
In article <3391EF2F.25DB@cip.mathematik.uni-stuttgart.de>,
haeberts@cip.mathematik.uni-stuttgart.de wrote:
> How many topologies (up to homeomorphism) can be defined on a finite set
> with n elements?
>
> Can anyone give me a good reference to the answer for that question? Is
> there a "simple" formula for the number of "different" topologies,
> depending on n? Or is this another simple question with a complicated
> answer?
>
The question of the number of topologies on a finite point set is
definitely a combinatorial one, and also probably impossible. There is no
known formula, although asymptotics are known. See
Kleitman, D., and Rothschild, B., ``The number of finite topologies'',
Proc. AMS, 25, 1970, 276-282.
and
Kleitman, D., and Rothschild, B., ``Asymptotic enumeration of
partial orders on a finite set'', Trans. Amer. Math. Soc. 205 (1975),
205--220.
For other references, consult
P. Renteln, ``On the enumeration of finite topologies'', Journal of
Combinatorics, Information, and System Sciences, 19 (1994) 201-206
The problem ``reduces'' to finding the number of partial orders on a
finite set, which is an equally intractable problem. You might want to
see
P. Renteln, ``Geometrical Approaches to the Enumeration of Finite
Posets: An
Introductory Survey'', Nieuw Archief voor Wiskunde, 14 (1996) 349-371.
and references therein.
--
Paul Renteln
Associate Professor
Department of Physics
California State University San Bernardino
5500 University Parkway
San Bernardino, CA 92407
prenteln@wiley.csusb.edu
******************************************************************
A man's life in these parts often depends on a mere scrap
of information.
The Gunslinger
Fistfull of Dollars
******************************************************************