
Re: Stone Cech
Posted:
Mar 22, 2013 11:52 AM


On Fri, 22 Mar 2013 08:43:53 0600, David C. Ullrich <ullrich@math.okstate.edu> wrote:
>On Fri, 22 Mar 2013 05:34:37 0500, quasi <quasi@null.set> wrote: > >>Butch Malahide wrote: >>>Butch Malahide wrote: >>>>Butch Malahide wrote: >>>>>quasi wrote: >>>>>>Butch Malahide wrote: >>>>>>>quasi wrote: >>>>>>>>quasi wrote: >>>>>>>>>quasi wrote: >>>>>>>>>>quasi wrote: >>>>>>>>>>>Butch Malahide wrote: >>>>>>>>>>>>David C. Ullrich wrote: >>>>>>>>>>>>>Butch Malahide wrote >>>>>>>>>>>>>>William Elliot wrote: >>>>>>>>>>>>>>>David Hartley wrote: >>>>>>>>>>>>>>>>William Elliot wrote: >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>Perhaps you could illustrate with the five >>>>>>>>>>>>>>>>>different one to four point point >>>>>>>>>>>>>>>>>compactifications of two open end line >>>>>>>>>>>>>>>>>segements. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>(There are seven.) >>>>>>>>>>>>>>> >>>>>>>>>>>>>>>Ok, seven nonhomeomophic finite Hausdorff >>>>>>>>>>>>>>>compactications. >>>>>>>>>>>>>> >>>>>>>>>>>>>>How many will there be if you start with n segments >>>>>>>>>>>>>>instead of 2? >>>>>>>>>>>>> >>>>>>>>>>>>>Surely there's no simple formula for that? >>>>>>>>>>>>> >>>>>>>>>>>>> ... >>>>>>>>>>>> >>>>>>>>>>>> ... >>>>>>>>>>>> >>>>>>>>>>>>I wasn't necessarily expecting a *complete* answer, >>>>>>>>>>>>such as an explicit generating function. Maybe someone >>>>>>>>>>>>could give a partial answer, such as an asymptotic >>>>>>>>>>>>formula, or nontrivial upper and lower bounds, or a >>>>>>>>>>>>reference to a table of small values, or the ID number >>>>>>>>>>>>in the Encyclopedia of Integer Sequences, or just the >>>>>>>>>>>>value for n = 3. (I got 21 from a hurried hand count.) >>>>>>>>>>> >>>>>>>>>>>For n = 3, my hand count yields 19 distinct >>>>>>>>>>>compactifications, up to homeomorphism. >>>>>>>>>>> >>>>>>>>>>>Perhaps I missed some cases. >>>>>>>>>>> >>>>>>>>>>I found 1 more case. >>>>>>>>>> >>>>>>>>>>My count is now 20. >>>>>>>>> >>>>>>>>>I found still 1 more case. >>>>>>>>> >>>>>>>>>So 21 it is! >>>>>>>>> >>>>>>>>>But after that, there are no more  I'm certain. >>>>>>>> >>>>>>>>Oops  the last one I found was bogus. >>>>>>>> >>>>>>>>So my count is back to 20. >>>>>>> >>>>>>>Hmm. I counted them again, and I still get 21. >>>>>>> >>>>>>>4 3component spaces: OOO, OO, O, . >>>>>>> >>>>>>>7 2component spaces: OO, O, O6, O8, , 6, 8. >>>>>>> >>>>>>>10 connected spaces: O, , 6, 8, Y, theta, dumbbell, and >>>>>>>the spaces obtained by taking a Y and gluing one, two, or >>>>>>>all three of the endpoints to the central node. >>>>>> >>>>>>Thanks. >>>>>> >>>>>>It appears I missed the plain "Y", but other than that, >>>>>>everything matches. >>>>>> >>>>>>So yes, 21 distinct types. >>>>> >>>>> For n = 4 I get 56 types. If I counted right (very iffy), >>>> >>>> Found two more. Never mind! >>> >>>And now I get 61. The hell with it. >> >>Ullrich predicted it (hopeless squared). > >Hey, you guys are making progress! >Now all we need is an f such that >f(2) = 7, f(3) = 21 or whatever it was, >and f(4) = 61. I doubt there's more than >one such f... > >> >>For small n, say n < 10, it might be feasible to get the counts >>via a computer program, but my sense is that the development of >>such a program would be fairly challenging. If I get a chance, >>I may give it a try. > >My prediiction is that anything remotely resembling brute >force will take forever to run, even in a compiled language. >Just enumerating all the possible equivalence relations >on 2n points is going to take a long time; now a >brute force check whether _one_ pair of equivalence >relations defines homeomorphic spaces will also take >a long time, and there will be N(N1)/2 such checks, >where N is huge even for small n.
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.
> >But don't let me stop you. I'd start in Python, which >would be much too slow  the point being that Python >is so easy to _write_ that it would be the quickest >way to get the algorithm straight. I'd test the >Python code for n = 2 and 3 maybe; for n = 3 >it would take forever. Once I had a correct >algorithm I'd rewrite it in a compiled language. >Then ask for the answer for n = 4 and maybe >take a trip somewhere while waiting for the >answer... > >> >>quasi

