Geometry of Graphs and Banach Spaces

一个人生活的世界本质上是几何的，在那里无数的日常生活问题，以及基本的科学奥秘，都可以用几何术语来表达。例如，对物理定律的研究导致了一种精细的数学框架的发展，在这种框架中，精细的几何结构能够描述基本粒子的相互作用和量子物理背后的对称性并建立模型。另一个例子来自网络，它在现代社会中无处不在。从万维网及其强大的搜索引擎到社交网络，从电信网络到经济系统，网络代表了广泛的现实世界系统。通过将网络中连接两个节点的最短路径的边数视为衡量它们的邻近度的量，自然可以将网络视为几何对象。图上的最短路径距离是一个称为“度量”的抽象数学对象的基本例子。度量空间的概念是一个重要的概念，它在网络优化问题的数学模型中以及在包括计算机视觉、计算生物学、机器学习、统计学和数学心理学在内的广泛应用领域中都是关键的。这个极其有用的抽象概念推广了欧几里得空间的经典概念，在欧几里得空间中，从点A到点B的距离是通过连接它们的直线的长度来计算的。在许多实际问题中，问题的核心可以归结为理解我们是否可以在我们更好地理解并带有额外结构的其他几何对象中找到给定度量空间的表示，特别是配备了其最短路径距离的图。我们以数量上有效的方式完成这项任务的能力具有巨大的应用价值。该项目将为本科生提供发展全球思维和卓越沟通技能的机会，并为研究生提供获得现代工作场所至关重要的算法和编程技能的机会。在这个项目中，PI建议在几个实例中实施几何方法，这是一种通过揭示隐藏的度量结构来理解和解决看似非几何性质的问题的策略，该结构允许应用大量强大的度量技术。由于它的多功能性，几何方法几乎渗透到了数学的所有领域。创建包含数十亿个条目的数据集已成为一项例行公事且无处不在的任务。在这些巨大的数据集上，优化、搜索和数据挖掘问题在计算上是极其困难的。图是许多数据集的自然数学模型，而计算机科学的一个核心任务是为各种图上的优化和搜索问题设计高效而快速的近似算法。图是一个看似非几何性质的组合对象。然而，一旦有了最短路径度量，图就变成了度量空间，图上支持的所有度量的集合带有几何信息，这些几何信息可以用来理解和研究图的组合结构。自90年代中期S兴起以来，到目前为止，利用图的几何嵌入，最著名的是嵌入到树度量或经典的勒贝格序列空间中，为计算困难的问题提供了优雅的、经常是最优的、有时甚至是唯一的逼近算法。这一建议的第一个目标是显著提高我们对有限度量的可嵌入性这一一般问题的理解。特别是，我们将从算法的角度研究照明器度量和瓦瑟斯坦度量之间的联系，以及与度量Kadec-Pelczynski问题相关的薄Laakso结构的几何。第二个目标是用几何方法解决拓扑学中的Novikov猜想和黎曼几何中的Gromov正标量曲率猜想，目的是显著提高我们对Banach空间的粗几何和Banach空间的渐近行为的理解，尤其是非局部有限图上的浓度不等与Szlenk指数之间的关系。这个奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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 arepresentation 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.