Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
David C. Ullrich

Posts: 21,553
Registered: 12/6/04
Re: Stone Cech
Posted: Mar 23, 2013 4:17 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Sat, 23 Mar 2013 18:58:53 +0000, Frederick Williams
<freddywilliams@btinternet.com> wrote:

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


That one's easy; f(n) = 1. You want to delete the "SC" here
and insert "finite", meaning "only finitely many added points".

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


Indeed. Nobody knows about anything here being actually intractable,
but yesterday I didn't see any way to write even a very bad program
to calculate f(n) for small n. The problem being, given two
equivalence relations on the set of 2n endpoints, to determine
whether the resulting compactifications are homeomorphic.

Not nearly as hard as it seemed to me yesterday, thanks to Mr.
Malahide.

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




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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.