"David C. Ullrich" wrote: > > On Fri, 22 Mar 2013 20:27:15 -0700 (PDT), Butch Malahide > <email@example.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