Geometry of Graphs and Banach Spaces

一个人生活的世界本质上是几何的，许多日常生活中的问题，以及基本的科学奥秘，都可以用几何术语表达。例如，对物理定律的研究已经导致了一个精确的数学框架的发展，在这个框架中，精细的几何结构能够描绘和模拟基本粒子的相互作用和量子物理学基础的对称性。另一个例子来自网络，它在现代社会中无处不在。从万维网及其强大的搜索引擎到社交网络，从电信网络到经济系统，网络代表了广泛的真实的世界系统。一个网络可以自然地被看作是一个几何对象，通过考虑连接网络中两个节点的最短路径的边的数量来衡量它们的接近程度。图上的最短路径距离是抽象数学对象“度量”的一个基本例子。度量空间的概念是一个总体概念，在网络优化问题的数学模型中以及在广泛的应用领域中至关重要，包括计算机视觉，计算生物学，机器学习，统计学和数学心理学，仅举几例。这个非常有用的抽象概念推广了欧几里得空间的经典概念，其中从点A到点B的距离被计算为连接它们的直线的长度。在许多实际问题中，问题的核心归结为理解我们是否可以找到一个给定的度量空间的表示，特别是一个配备了最短路径距离的图，在一些其他的几何对象中，我们更好地理解，并携带额外的结构。我们以定量有效的方式执行这样一项任务的能力具有巨大的应用价值。该项目将为本科生提供培养全球思维和上级沟通技能的机会，并为研究生提供获得现代工作场所所急需的算法和编程技能的机会。在这个项目中，PI建议在几个实例中实施几何方法，这是一种通过揭示隐藏的度量结构来理解和解决看似非几何性质的问题的策略，该结构允许应用大量强大的度量技术。由于它的通用性，几何方法几乎渗透到了数学的所有领域。创建具有数十亿条目的数据集已成为一项常规且无处不在的任务。在这些庞大的数据集上进行优化、搜索和数据挖掘问题在计算上非常难以解决。图是许多数据集的自然数学模型，计算机科学的一个中心任务是为各种图上的优化和搜索问题设计高效快速的近似算法。图是一个看似非几何性质的组合对象。然而，一旦配备了最短路径度量，图就成为度量空间，并且图上支持的所有度量的集合携带可用于理解和研究图的组合结构的几何信息。在90年代中期兴起之后，现在有许多情况下，利用图的几何嵌入，最值得注意的是嵌入到树度量或经典勒贝格序列空间中，提供了优雅的，通常是最佳的，并且在某些情况下是计算上难以解决的问题的唯一近似算法。 这个建议的第一个目标是大大提高我们对有限度量可嵌入性的一般问题的理解。特别是，我们将调查点灯度量和Wasserstein度量之间的连接从算法的角度来看，和薄Laakso结构的几何关系的度量Kadec-Pelczynski问题。第二个目标是通过拓扑学中诺维科夫猜想和黎曼几何中格罗莫夫正数量曲率猜想的几何方法来推动我们对Banach空间的粗几何和Banach空间的渐进行为的理解，最明显的是非集中不平等之间的关系，该奖项反映了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.