How Many Topologies on a Finite Set?
Thomas Haeberlen
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 "standard textbooks" in Topology don't seem to deal with this
question so I wonder where the answer could be found. Maybe it can be
given by using Combinatorics or something like that?
Any hints will be appreciated. Thanks in advance.
Thomas Haeberlen
--
Email: haeb...@cip.mathematik.uni-stuttgart.de
WWW: http://www.mathematik.uni-stuttgart.de/CIP/haeberts/homepage.html
Richard Bumby
Thomas Haeberlen <haeb...@cip.mathematik.uni-stuttgart.de> 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?
>...............<snip>.............
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
bu...@math.rutgers.edu ||
bu...@dimacs.rutgers.edu || Phone: [USA] 908 445 0277 * FAX 908 445 5530
Dave Rusin
Thomas Haeberlen wrote:
> How many topologies (up to homeomorphism) can be defined on a finite set
> with n elements?
There's no simple formula known. For some discussion and pointers see
http://www.math.niu.edu/~rusin/known-math/point-set.top/finite.top
(If s.m.r. ever gets its own FAQ, this question will have to be there.)
dave
Paul Renteln
In article <3391EF...@cip.mathematik.uni-stuttgart.de>,
haeb...@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
******************************************************************
A man's life in these parts often depends on a mere scrap
of information.
The Gunslinger
Fistfull of Dollars
******************************************************************
Mark Davis
In article <5mts7n$7at$1...@artemis.it.luc.edu>,
Michael Smith <msm...@orion.it.luc.edu> wrote:
>Maybe this will help.
>
>Any topology is essentially a collection of open sets. Furthermore one
>can uniquely determine the topology on a space X based on a collection
>of subsets known as a sub-basis, S, which has the property that any
>point in X belongs to at least one set in the sub-basis. Given S, we
>can determine the topology on X by using two rules:
>
>1) Any base set is a finite intersection of sets in the sub-basis
>2) Any open set in X is an arbitrary union of base sets.
>
>I'm going to make a conjecture here. Please feel free to contradict it
>or to ignore it. If I come up with a proof I'll post it.
>
>Conjecture: every topology on a finite, nonempty space has a unique
>sub-basis S0 which meets the conditions that:
> a) the empty set is not an member of S0
> b) the intersection of any two member sets in S0 is empty.
>
>If this conjecture holds true, then there are as many topologies on a
>set of N elements as there are ways to partition a set of N elements
>into disjoint subsets.
This conjecture doesn't hold. Let X = {1,2,3}, T = {{},{1},{1,2},X}. T has
no subbase of the kind you conjecture. If we remove either of {1},{1,2} from
T the resulting set does not generate T, so any subbase contains {1} and
{1,2} which have nonempty intersection.
Mark Davis.
[ moderator's note: yesterday I posted a similar "counterexample" involving
a two-point set: {a,b} with topology {},{a},{a,b}. However, that one was
incorrect because you could use subbase {{a}} (and get {a,b} as the
intersection of the empty subset of this). Mark's counterexample works,
though. ]