School of Mathematics

Vertex Sparsification: An Introduction, Connections and Applications

Ankur Moitra
Massachusetts Institute of Technology; Institute for Advanced Study
November 8, 2011

The notion of exactly (or approximately) representing certain combinatorial properties of a graph $G$ on a simpler graph is ubiquitous in combinatorial optimization. In this talk, I will introduce the notion of vertex sparsification. Here we are given a graph $G = (V, E)$ and a set of terminals $K \subset V$ and our goal is to find one single graph $H = (K, E_H)$ on just the terminal set so that $H$ approximately preserves the minimum cut between every bi-partition of the terminals.

Strong and Weak Epsilon Nets and Their Applications

Noga Alon
Tel Aviv University; Institute for Advanced Study
November 7, 2011

I will describe the notions of strong and weak epsilon nets in range spaces, and explain briefly some of their many applications in Discrete Geometry and Combinatorics, focusing on several recent results in the investigation of the extremal questions that arise in the area, and mentioning some of the remaining open problems.

Characteristic Polynomials of the Hermitian Wigner and Sample Covariance Matrices

Tatyana Shcherbina
Institute for Low Temperature Physics, Kharkov
November 1, 2011

We consider asymptotics of the correlation functions of characteristic polynomials of the hermitian Wigner matrices $H_n=n^{-1/2}W_n$ and the hermitian sample covariance matrices $X_n=n^{-1}A_{m,n}^*A_{m,n}$. We use the integration over the Grassmann variables to obtain a convenient integral representation.