One of the great things about going to Mathcamp is the chance to attend other people’s classes. The first two weeks I was teaching or coteaching 2 classes per day, so I didn’t get a chance to attend many classes. I’ve been making up for that in the past two weeks, going to classes on geometric group theory, nonstandard analysis, hyperbolic geometry, and the probabilistic method. I really enjoy going to other people’s classes because it gives a good window into other young mathematicians taste in mathematics. It’s often hard to see what people really love just by looking at their research, but what people teach at Mathcamp is almost always what’s close to their hearts.
I’m going to try to put some posts up on my favorite aspects of the classes that I’ve gone to. First off, the probabalistic method was taught by Matt Kahle who just graduated from Washington, and is starting a postdoc at Stanford. His research is in the asymptotic combinatorics of topology and geometry. Although there were definitely some more spectacular applications of the probabilistic method, one stood out for its simplicity.
Consider a graph G with n edges. We claim that there exists a bipartite subgraph with at least n/2 edges. How can you produce all bipartite subgraphs? Clearly, you just split the vertices of G into 2 sets, A and B, and only keep the edges between A and B. Let’s just do this <i>randomly</i>. That is to say, for each vertex indepently put it into A with probability 1/2, and B with probability 1/2. What’s the expected number of edges between A and B? Well, each edge is AA, AB, BA, or BB, so with 1/2-probability the edge goes between A and B. But since expectation is additive (even when the events aren’t independent!) the total expected number of edges between A and B is n/2. But this means there must be at least one bipartite subgraph with n/2 edges!
Secret Blogging Seminar 