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