Mathematics

Colour ${1,\ldots,N}$ red and blue, in such a manner that no 3 of the blue elements are in arithmetic progression. How long an arithmetic progression of red elements must there be? It had been speculated based on numerical evidence that there must always be a red progression of length about $\sqrt{N}$. I will describe a construction which shows that this is not the case - in fact, there is a colouring with no red progression of length more than about $\exp{\left(\left(\log{N}\right)^{3/4}\right)}$, and in particular less than any fixed power of $N$.

I will give a general overview of this kind of problem (which can be formulated in terms of finding lower bounds for so-called van der Waerden numbers), and an overview of the construction and some of the ingredients which enter into the proof. The collection of techniques brought to bear on the problem is quite extensive and includes tools from diophantine approximation, additive number theory and, at one point, random matrix theory

A connected matching is a matching contained in a connected component. A well-known method due to Łuczak reduces problems about monochromatic paths and cycles in complete graphs to problems about monochromatic matchings in almost complete graphs. We show that these can be further reduced to problems about monochromatic connected matchings in complete graphs.

I will describe Łuczak's reduction, introduce the new reduction, and mention potential applications of the improved method.

Suppose you want to open up 7 coffee shops so that people in the downtown area have to walk the least amount to get their morning coffee. That’s a classical problem in Optimal Transport, minimizing the Wasserstein distance between the sum of 7 Dirac measures and the (coffee-drinking) population density. But in reality things are trickier. If the 7 coffee shops go well, you want to open an 8th and a 9th and you want to remain optimal in this respect (and the first 7 are already fixed). We find optimal rates for this problem in ($W_2$) in all dimensions. Analytic Number Theory makes an appearance and, in fact, Optimal Transport can tell us something new about $\sqrt{2}$ . All of this is also related to the question of approximating an integral by sampling in a number of points and a conjectured extension of the Kantorovich-Rubinstein duality regarding the $W_1$ distance and testing of two measures against Lipschitz functions.

The past decade has seen a rapid development of data-driven plant breeding strategies based on the two significant technological developments. First, the use of high throughput DNA sequencing technology to identify millions of genetic markers on that characterize the available genetic diversity captured by the thousands of available accessions in each major crop species. Second, the development of high throughput imaging platforms for estimating quantitative traits associated with easily accessible above-ground structures such as shoots, leaves and flowers. These data-driven breeding strategies are widely viewed as the basis for rapid development of crops capable of providing stable yields in the face of global climate change. Roots and other below-ground structures are much more difficult to study yet play essential roles in adaptation to climate change including as uptake of water and nutrients. Estimation of quantitative traits from images remains a significant technical and scientific bottleneck for both above and below-ground structures. The focus of this talk, inspired by the analytical results of Kac, van den Berg and many others in the area of spectral geometry, is to describe a computational and statistical methodology that employs stochastic processes as quantitative measurement tools suitable for characterizing images of multi-scale dendritic structures such as plant root systems. The substrate for statistical analyses in Wasserstein space are hitting distributions obtained by simulation. The practical utility of this approach is demonstrated using 2D images of sorghum roots of different genetic backgrounds and grown in different environments.

Optimal transport (OT) has recently gained lot of interest in machine learning. It is a natural tool to compare in a geometrically faithful way probability distributions. It finds applications in both supervised learning (using geometric loss functions) and unsupervised learning (to perform generative model fitting). OT is however plagued by the curse of dimensionality, since it might require a number of samples which grows exponentially with the dimension. In this talk, I will explain how to leverage entropic regularization methods to define computationally efficient loss functions, approximating OT with a better sample complexity. More information and references can be found on the website of our book “Computational Optimal Transport” https://optimaltransport.github.io/