Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Stone Cech
Replies: 49   Last Post: Mar 28, 2013 12:15 PM

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 Butch Malahide Posts: 894 Registered: 6/29/05
Re: Stone Cech
Posted: Mar 22, 2013 11:27 PM
 Plain Text Reply

On Mar 22, 10:52 am, David C. Ullrich <ullr...@math.okstate.edu>
wrote:
> I just realized I have no idea whatever how to write
> a correct algorithm here, even without worrying
> about efficiency.
>
> An equivalence relation on the 2n endpoints
> determines a compactification. It also determines
> a graph, where the vertices are the equivalence
> classes of endpoints and the edges are the
> original segments. Earlier, thinking that I was
> thinking about deciding when two of these
> compactifications are homeomorphic, I was
> actually thinking about how to determine
> whether two of the graphs are isomorphic.
> That's a strictly weaker condition... I have
> no idea how I'd check whether two equivalences
> gave homeomorphic compactifications.

You mean, non-isomorphic is a weaker condition than non-homeomorphic.

The remedy for that is to stick to graphs with no vertices of degree
2. (OK, you have to make an exception for the graph consisting of a
single vertex of degree 2, corresponding to the one-point
compactification of R.)

All right, the problem is to determine the number of nonisomorphic
pseudographs (undirected graphs which may have loops and multiple
edges) with p vertices and q edges, and with no vertices of degree 2.
(Alternatively, determine the number of nonisomorphic *connected*
pseudographs with p vertices, q edges, and no vertices of degree 2.)
Since we are counting isomorphism types, it's a problem for Burnside-
Polya-Redfield enumeration theory. Which I'm not well enough
acquainted with to know the difference between a merely difficult
problem and an impossible problem, so I have to take your word for it
that it's impossible.

All right, but what about the order-of-magnitude or asymptotic
problem, which was also implicit in my open-ended "how many" question?
Does f(n)^(1/n) approach a limit? Is that also hopeless?

Date Subject Author
3/14/13 William Elliot
3/14/13 fom
3/15/13 fom
3/16/13 William Elliot
3/15/13 David C. Ullrich
3/17/13 William Elliot
3/17/13 David C. Ullrich
3/17/13 fom
3/18/13 David C. Ullrich
3/18/13 fom
3/18/13 David Hartley
3/19/13 William Elliot
3/19/13 David Hartley
3/19/13 William Elliot
3/20/13 Butch Malahide
3/20/13 David C. Ullrich
3/20/13 Butch Malahide
3/20/13 Butch Malahide
3/21/13 quasi
3/21/13 quasi
3/21/13 quasi
3/21/13 quasi
3/21/13 Butch Malahide
3/21/13 quasi
3/22/13 Butch Malahide
3/22/13 Butch Malahide
3/22/13 Butch Malahide
3/22/13 quasi
3/22/13 David C. Ullrich
3/22/13 David C. Ullrich
3/22/13 Butch Malahide
3/23/13 Butch Malahide
3/23/13 David C. Ullrich
3/23/13 David C. Ullrich
3/23/13 Frederick Williams
3/23/13 David C. Ullrich
3/23/13 Frederick Williams
3/22/13 Butch Malahide
3/23/13 David C. Ullrich
3/22/13 Butch Malahide
3/23/13 quasi
3/23/13 Butch Malahide
3/23/13 Butch Malahide
3/24/13 quasi
3/24/13 Frederick Williams
3/24/13 quasi
3/25/13 Frederick Williams
3/28/13 Frederick Williams
3/25/13 quasi
3/19/13 David C. Ullrich

© The Math Forum at NCTM 1994-2018. All Rights Reserved.