DECEMBER 2009

A homogeneous set in a graph G is a subset X of V(G), such that no vertex of V(G)\X has both a neighbor and a non-neighbor in X. Let us say that a graph is prime if it has no homogeneous set X with 1<|X|<|V(G)|.

Seymour's well-known splitter theorem states that if G and H are 3-connected graphs, G is not a wheel, H is not the complete graph on four vertices, and H is a minor of G, then G can be built from H by undeleting or uncontracting one edge at a time, and so that all the graphs constructed along the way are 3-connected. We prove a similar result for the induced subgraph containment relation, replacing 3-connected with prime, undeleting and uncontracting with adding a vertex, and wheels with a certain family of bipartite graphs that we call B. We prove that if G and H are prime graphs, G is not in B, and H is an induced subgraph of G, then G can be built from H, adding one vertex at a time, and so that all the graphs constructed along the way are prime.

We then use this result to prove that every n-vertex prime claw-free graph has at most n+1 simplicial cliques (a clique C of G is simplicial if for every vertex c of C, the set of neighbors of c outside of C is a clique). This allows us to test in polynomial time if a claw-free graph has a simplicial clique, answering a question of Prasad Tetali.

This is joint work with Paul Seymour.

Mean curvature flow (or MCF) is a nonlinear heat equation for hyper-surfaces, where the surface evolves by moving in the direction where volume locally decreases the fastest. The simplest non-static examples are round concentric spheres, where the radius shrinks until it becomes zero at "extinction" (a singularity of the flow). Singularities are unavoidable as the flow contracts any closed surface and thus one of the most important problems in MCF is understanding the singularities. Matt Grayson, Mike Gage and Richard Hamilton proved that this is the only singularity for simple closed curves in the plane. However, many examples were discovered in higher dimensions.

I will describe recent work with Toby Colding, MIT, where we:
1. Classify the generic singularities of MCF of closed embedded hyper-surfaces.
2. Prove compactness of all (even non-generic) singularities.
I will also discuss an application, where we construct a "generic mean curvature flow".

The universality for eigenvalue spacing distributions is a central question in the random matrix theory. In this talk, we introduce a new general approach based on comparing the Dyson Brownian motion with a new related dynamics, the local relaxation flow. This method can be applied to prove the universality for the eigenvalue spacing distributions for the symmetric, hermitian, self-dual quaternion matrices and the real and complex Wishart matrices. A central tool in this approach is to estimate the entropy flow via the logarithmic Sobolev inequality.

One of the main goals of the theory of random matrices is to establish the limiting distributions of the eigenvalues. In the 1950s, Wigner proved his famous semi-cirle law (subsequently extended by Anord, Pastur and others), which established the global distribution of the eigenvalues of random Hermitian matrices. In the last fifty years or so, the focus of the theory has been on the local distributions, such as the distribution of the gaps between consecutive eigenvalues, the k-point correlations, the local fluctuation of a particular eigenvalue, or the distribution of the least singular value. Many of these problems have connections to other fields of mathematics, such as combinatorics, number theory, statistics and numerical linear algebra.

Most of the local statistics can be computed explicitly for random matrices with gaussian entries (GUE or GOE), thanks to Ginibre's formulae of the joint density of eigenvalues. It has been conjectured that these results can be extended to other models of random matrices. This is generally known as the Universality phenomenon, with several specific conjectures posed by Wigner, Dyson, Mehta etc. 

In this talk, we would like to discuss recent progresses concerning the Universality phenomenon, focusing on a recent result (obtained jointly with T. Tao), which asserts that all local statistics of eigenvalues of a random matrix are determined by the first four moments of the entries. This (combining with results of Johansson, Erdos-Ramirez-Schlein-Yau and many others) provides the answer to several old problems.