Andy's Math/CS page

Friday, April 21, 2006

Riffing on Topology

First, let it be known that I'm enrolling in CS graduate studies at UC San Diego this fall. If anyone reading has leads on cheap housing, running trails, or any other tips on the area, I'd love to hear. Also, I'll probably be in Amherst, MA this summer, with time on my hands and complexity theory on my mind.

It's been a very busy semester, due in part to my Topology double-credit seminar. I've mostly been playing by the rules and haven't felt all that creative in the class, but recently something came up.

We're working out of James Munkres' textbook. One of the culminating chapters uses topology (specifically, homotopy and the construction of covering spaces) to prove a purely group-theoretical result: that subgroups of a free group are free.

Cross-fertilization of disciplines is always neat; however, when I imagine reading this proof from the point of view of someone devoted to group theory, I really want to know how much topological structure is necessary to the basic proof idea. The proof here is not too hard once you've spent the overhead to get the Siefert-Van-Kampen Theorem (to compute 1st homotopy groups of complex spaces) and the general constructibility of covering spaces (certainly worthwhile for topologists); but what if you wanted just the group theory output? We've seen that topological spaces support free-subgroup structure, but could a more restricted, simple cass of objects do it more efficiently?

The book proof has the following outline: Given a free group G and a subgroup H, construct a topological graph X_G that has (by S-V-K) G as its 1st homotopy group; construct (using the general theorem) a covering space C of X_G that has induced homotopy subgroup H; conclude that C has H as its 1st homotopy group; prove that C must be a graph; prove that graphs have free homotopy groups, hence H is free.

My feeling was that free groups are very naturally associated, not just with topological graphs (i.e., where edges are considered continua), but with combinatorial ones too (where edges are just ordered pairs of vertices); and that here, developing a homotopy theory would be much simpler since walks on combinatorial graphs are discrete entities and don't have such infinite wiggling diversity as walks in continua. In fact, the connection becomes almost axiomatic because the basic allowable transformation in my kind of homotopy--inserting an edge and its immediate reversal into a path--is 'just like' the cancellation rule a*a^{-1} = id that's operative in group theory. The covering space theory I hoped I could import by direct analogy.

Anyways, executing this was a draining process (new theory --> need for careful exposition), but I think I've been more-or-less successful. For anyone interested:

Graph Homotopy and the Free Subgroup Theorem

I haven't scoped around for this exact theory appearing elsewhere, but I'm becoming aware that combinatorializing topological structures is by now a time-honored procedure. However, I'm glad to have gotten acquainted with it thru personal activity, that moreover helped me review the coursework.