On Sat, 23 Mar 2013 18:58:53 +0000, Frederick Williams <email@example.com> wrote:
>"David C. Ullrich" wrote: >> >> On Fri, 22 Mar 2013 20:27:15 -0700 (PDT), Butch Malahide >> <firstname.lastname@example.org> 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.