Georgia Institute of Technology College of Sciences

From time to time a new algorithm comes along that causes a sensation in theoretical computer science or in an area of application because of its resolution of a long-standing open question, its surprising efficiency, its practical usefulness, the novelty of its setting or approach, the elegance of its structure, the subtlety of its analysis or its range of applications. We will give examples of algorithms that qualify for greatness for one or more of these reasons, and discuss how to equip students to appreciate them and understand their strengths and weaknesses.

The class of random regular graphs has been the focus of extensive study highlighting the excellent expansion properties of its typical instance. For instance, it is well known that almost every regular graph of fixed degree is essentially Ramanujan, and understanding this class of graphs sheds light on the general behavior of expanders. In this talk we will present several recent results on random regular graphs, focusing on the interplay between their spectrum and geometry. We will first discuss the relation between spectral properties and the abrupt convergence of the simple random walk to equilibrium, derived from precise asymptotics of the number of paths between vertices. Following the study of the graph geometry we proceed to its random perturbation via exponential weights on the edges (first-passage-percolation). We then show how this allows the derivation of various properties of the classical Erd\H{o}s-R\'enyi random graph near criticality. Finally, returning to the spectrum of random regular graph, we discuss the question of how close they really are to being Ramanujan and conclude with related problems involving random matrices. Based on joint works with Jian Ding, Jeong Han Kim and Yuval Peres, with Allan Sly and with Benny Sudakov and Van Vu.

I will review recent and classical results concerning the asymptotic properties (as N --> \infty) of 'ground state' configurations of N particles restricted to a d-dimensional compact set A\subset {\bf R}^p that minimize the Riesz s-energy functional \sum_{i\neq j}\frac{1}{|x_{i}-x_{j}|^{s}} for s>0. Specifically, we will discuss the following (1) For s < d, the ground state configurations have limit distribution as N --> \infty given by the equilibrium measure \mu_s, while the first order asymptotic growth of the energy of these configurations is given by the 'transfinite diameter' of A. (2) We study the behavior of \mu_s as s approaches the critical value d (for s\ge d, there is no equilibrium measure). In the case that A is a fractal, the notion of 'order two density' introduced by Bedford and Fisher naturally arises. This is joint work with M. Calef. (3) As s --> \infty, ground state configurations approach best-packing configurations on A. In work with S. Borodachov and E. Saff we show that such configurations are asymptotically uniformly distributed on A.

The Jacobian of a graph, also known as the Picard Group, Sandpile Group, or Critical Group, is a discrete analogue of the Jacobian of an algebraic curve. It is known that the order of the Jacobian of a graph is equal to its number of spanning trees, but the exact structure is known for only a few classes of graphs. In this talk I will present a combinatorial method of approaching the Jacobian of graphs by way of a chip-firing game played on its vertices. We then apply this chip-firing game to explicitly characterize the Jacobian of nearly complete graphs, those obtained from the complete graph by deleting either a cycle or two vertex-disjoint paths incident with all but one vertex. This is joint work with Sergey Norin.