
Re: Stone Cech
Posted:
Mar 22, 2013 11:27 PM


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, nonisomorphic is a weaker condition than nonhomeomorphic.
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 onepoint 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 PolyaRedfield 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 orderofmagnitude or asymptotic problem, which was also implicit in my openended "how many" question? Does f(n)^(1/n) approach a limit? Is that also hopeless?

