Geometry of Graphs and Banach Spaces

The world one lives in is geometric in nature where numerous everyday-life issues, as well as fundamental scientific mysteries, can be expressed in geometric terms. For instance, the study of physical laws has led to the development of a refined mathematical framework where elaborate geometric structures are able to depict and model the interactions of elementary particles and the

symmetries underlying quantum physics. Another example comes from networks, which are ubiquitous in modern society. From the World Wide Web and its powerful search engines to social networks, from telecommunication networks to economic systems, networks represent a wide range of real world systems. A network can naturally

be seen as a geometric object by considering the number of edges of the shortest path connecting two nodes in the network as a quantity measuring their proximity. The shortest path distance on a graph is a fundamental example of an abstract mathematical object called "metric". The notion of a metric space is

an overarching concept that is pivotal in mathematical models of optimization problems in networks, and in a vast range of application areas, including computer vision, computational biology, machine learning, statistics, and mathematical psychology, to name a few. This extremely useful abstract concept

generalizes the classical notion of a Euclidean space, where the distance from point A to point B is computed as the length of a straight line connecting them. In numerous practical problems, the heart of the matter boils down to understanding whether we can find a representation of a given metric space, in particular a graph equipped with its shortest path distance,

inside some other geometric object that we understand much better and that carries additional structure. Our ability to perform such a task in a quantitatively efficient way has tremendous applications. The project will provide opportunities for undergraduate students to develop a global mindset and superior communication skills, and graduate

students to acquire the algorithmic and programming skills that are crucially needed in the modern workplace. In this project, the PI proposes to implement in several instances the geometric approach, which is a strategy that consists in understanding and solving problems of seemingly non-geometric nature via the

uncovering of a hidden metric structure that allows the application of a wealth of powerful metric techniques. Due to its versatility, the geometric approach has permeated virtually all fields of mathematics. Creating datasets with billions of entries has become a routine and ubiquitous task. Optimization, search, and data mining problems on these huge datasets are computationally extremely

hard to solve. Graphs are natural mathematical models for many datasets, and a central computer science task is the design of efficient and fast approximation algorithms for optimization and search problems on various graphs. A graph is a combinatorial object of seemingly non-geometric nature. However, once equipped with a shortest path metric a graph becomes a metric space and the collection

of all metrics supported on the graph carries geometric information that can be used to understand and study the combinatorial structure of the graph. After its rise in the mid-90's, there are by now numerous situations where availing to geometric embeddings of graphs, most notably embeddings into tree-

metrics or into the classical Lebesgue sequence spaces, provides elegant, very often optimal, and on some occasions the only approximation algorithms for computationally intractable problems. The first goal of this proposal is to advance significantly our understanding of the general problem of embeddability of finite metrics. In particular, we will investigate the connection between

lamplighter metrics and Wasserstein metrics from an algorithmic perspective, and the geometry of thin Laakso structures in relation to the Metric Kadec-Pelczynski Problem. The second goal, which is motivated by the geometric approach to the Novikov conjecture in topology and to Gromov's positive scalar curvature conjecture in Riemannian geometry, is to advance significantly our understanding of the

coarse geometry of Banach spaces and the asymptotic behavior of Banach spaces, most notably the relationship between concentration inequalities on non-locally finite graphs and the Szlenk index.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.