Georgia Institute of Technology College of Sciences

Expanders via Random Spanning Trees Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two random spanning trees approximates the expansion of every cut of the graph to within a factor of O(log n). For the random graph G_{n,p}, for p > c (log n)/n, two spanning trees give an expander. This is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. The construction of the splicer is elementary — each spanning tree can be produced independently using an algorithm by Aldous and Broder: a random walk in the graph with edges leading to previously unvisited vertices included in the tree. A second important application of splicers is to graph sparsification where the goal is to approximate every cut (and more generally the quadratic form of the Laplacian) using only a small subgraph of the original graph. Benczur-Karger as well as Spielman-Srivastava have shown sparsifiers with O(n log n/eps^2) edges that achieve approximation within factors 1+eps and 1-eps. Their methods, based on independent sampling of edges, need Omega(n log n) edges to get any approximation (else the subgraph could be disconnected) and leave open the question of linear-size sparsifiers. Splicers address this question for random graphs by providing sparsifiers of size O(n) that approximate every cut to within a factor of O(log n). This is joint work with Navin Goyal and Santosh Vempala.

The usual boundary condition adjoined to a second order elliptic equation is the Dirichlet problem, which prescribes the values of the solution on the boundary. In many applications, this is not the natural boundary condition. Instead, the value of some directional derivative is given at each point of the boundary. Such problems are usually considered a minor variation of the Dirichlet condition, but this talk will show that this problem has a life of its own. For example, if the direction changes continuously, then it is possible for the solution to be continuously differentiable up to a merely Lipschitz boundary. In addition, it's possible to get smooth solutions when the direction changes discontinuously as well.

We will begin with an overview of the Burau representation of the braid group. This will be followed by an introduction to a contact category on 3-manifolds, with a brief discussion of its relation to the braid group.

Let I_\alpha be the fractional integral operator. The Olsen inequality, useful in certain PDEs, concerns multiplication operators and fractional integrals in the L^p-norm, or more generally, the Morrey norm. We strenghten this inequality from the one given by Olsen.