Georgia Institute of Technology College of Sciences

The classic 1935 paper of Erdos and Szekeres entitled ``A combinatorial problem in geometry" was a starting point of a very rich discipline within combinatorics: Ramsey theory. In that paper, Erdos and Szekeres studied the following geometric problem. For every integer n \geq 3, determine the smallest integer ES(n) such that any set of ES(n) points in the plane in general position contains n members in convex position, that is, n points that form the vertex set of a convex polygon. Their main result showed that ES(n) \leq {2n - 4\choose n-2} + 1 = 4^{n -o(n)}. In 1960, they showed that ES(n) \geq 2^{n-2} + 1 and conjectured this to be optimal. Despite the efforts of many researchers, no improvement in the order of magnitude has been made on the upper bound over the last 81 years. In this talk, we will sketch a proof showing that ES(n) =2^{n +o(n)}.

A well-known theorem of Kuratowski (1930) in graph theory states that a graph is planar if, and only if, it does not contain a subdivision of $K_5$ or $K_{3,3}$. Wagner (1937) gave a structural characterization of graphs containing no subdivision of $K_{3,3}$. Seymour in 1977 and, independently, Kelmans in 1979 conjectured that if a graph does not contain a subdivision of $K_5$ then it must be planar or contain a set of at most 4 vertices whose removal results in a disconnected graph. In this talk, I will discuss additional background on this conjecture (including connection to the Four Color Theorem), and outline our recent proof of this conjecture (joint work with Dawei He and Yan Wang). I will also mention several problems that are related to this conjecture or related to our approach.

Modern imaging data are often composed of several geometrically distinct constituents. For instance, neurobiological images could consist of a superposition of spines (pointlike objects) and dendrites (curvelike objects) of a neuron. A neurobiologist might then seek to extract both components to analyze their structure separately for the study of Alzheimer specific characteristics. However, this task seems impossible, since there are two unknowns for every datum. Compressed sensing is a novel research area, which was introduced in 2006, and since then has already become a key concept in various areas of applied mathematics, computer science, and electrical engineering. It surprisingly predicts that high-dimensional signals, which allow a sparse representation by a suitable basis or, more generally, a frame, can be recovered from what was previously considered highly incomplete linear measurements, by using efficient algorithms. Utilizing the methodology of Compressed Sensing, the geometric separation problem can indeed be solved both numerically and theoretically. For the separation of point- and curvelike objects, we choose a deliberately overcomplete representation system made of wavelets (suited to pointlike structures) and shearlets (suited to curvelike structures). The decomposition principle is to minimize the $\ell_1$ norm of the representation coefficients. Our theoretical results, which are based on microlocal analysis considerations, show that at all sufficiently fine scales, nearly-perfect separation is indeed achieved. This project was done in collaboration with David Donoho (Stanford University) and Wang-Q Lim (TU Berlin).

This Colloquium will be Part II of the Stelson Lecture. A function of many variables, when chosen at random, is typically very complex. It has an exponentially large number of local minima or maxima, or critical points. It defines a very complex landscape, the topology of its level lines (for instance their Euler characteristic) is surprisingly complex. This complex picture is valid even in very simple cases, for random homogeneous polynomials of degree p larger than 2. This has important consequences. For instance trying to find the minimum value of such a function may thus be very difficult. The mathematical tool suited to understand this complexity is the spectral theory of large random matrices. The classification of the different types of complexity has been understood for a few decades in the statistical physics of disordered media, and in particular spin-glasses, where the random functions may define the energy landscapes. It is also relevant in many other fields, including computer science and Machine learning. I will review recent work with collaborators in mathematics (A. Auffinger, J. Cerny) , statistical physics (C. Cammarota, G. Biroli, Y. Fyodorov, B. Khoruzenko), and computer science (Y. LeCun and his team at Facebook, A. Choromanska, L. Sagun among others), as well as recent work of E. Subag and E.Subag and O.Zeitouni.