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