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

 Messages: [ Previous | Next ]
 Frederick Williams Posts: 2,164 Registered: 10/4/10
Re: Stone Cech
Posted: Mar 23, 2013 2:58 PM

"David C. Ullrich" wrote:
>
> On Fri, 22 Mar 2013 20:27:15 -0700 (PDT), Butch Malahide
> <fred.galvin@gmail.com> wrote:
>

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

>
> No, this is not something you should take my word for! Sounds
> like you know more about such things than I do - I was just
> conjecturing it was "impossible".

May I ask what the intractable problem is? (My apologies if it's been
made clear and I've missed it.) Let f(n) be the number of SC
compactifications of n open line segments. Is it "find a formula for
f(n)"? Or is it "evaluate f(n) for various n"? I know that they are
both problems, but the second may be intractable in a computing sense
independently of the first being intellectually demanding. Mayn't it?
It seems that one might program a computer to evaluate f(n) even if no
formula has been found.

> >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?

>
> I certainly don't know. My wild-ass guess is maybe. Seems like
> this question is more likely than the other of being susceptible
> to some clever idea, although I have no idea what that idea might be,
> not being all that clever.

--
When a true genius appears in the world, you may know him by
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

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