Geometry of Graphs and Banach Spaces

图几何和 Banach 空间

基本信息

批准号：
2055604
负责人：
Florent Baudier
金额：
$ 24.95万
依托单位：
Texas A&M University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-07-01 至 2025-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2055604&HistoricalAwards=false
关键词：
Geometry Graphs 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 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.

一个人生活的世界本质上是几何学，可以用几何学来表达许多日常生活问题以及基本的科学奥秘。例如，对物理定律的研究导致了一个精致的数学框架的发展，在该框架中，精致的几何结构能够描绘和建模基本颗粒和量子物理基础的对称性的相互作用。另一个例子来自现代社会中无处不在的网络。从万维网及其强大的搜索引擎到社交网络，从电信网络到经济系统，网络代表了广泛的现实世界系统。通过考虑将网络中两个节点连接的最短路径的边数作为测量其接近度的数量，可以自然地将网络视为几何对象。图上的最短路径距离是称为“度量”的抽象数学对象的基本示例。公制空间的概念是一个总体概念，在网络优化问题的数学模型以及包括计算机视觉，计算生物学，机器学习，统计和数学心理学等广泛的应用领域的数学模型中至关重要。这个非常有用的抽象概念概述了欧几里得空间的经典概念，其中从点A到点B的距离被计算为连接它们的直线的长度。在许多实际问题中，问题的核心归结为理解我们是否可以找到给定的度量空间的代表，尤其是配备了最短路径距离的图，在其他一些几何对象中，我们对我们了解得更好并且具有额外结构的其他几何对象。我们以定量有效的方式执行此类任务的能力具有巨大的应用。该项目将为本科生提供发展全球心态和卓越沟通技巧的机会，并研究生获得现代工作场所中至关重要的算法和编程技能。在该项目中，PI提议在多种情况下实施几何方法，该方法是通过揭示隐藏的度量结构来理解和解决看似非几何本质的问题的策略，该策略允许应用大量强大的度量技术。由于其多功能性，几何方法几乎渗透到数学的所有领域。创建具有数十亿个条目的数据集已成为一项常规和无处不在的任务。这些巨大数据集上的优化，搜索和数据挖掘问题在计算上很难解决。图是许多数据集的自然数学模型，中央计算机科学任务是设计高效且快速近似算法的设计，以优化和搜索各种图表。图是看似非几何特性的组合对象。但是，一旦配备了最短的路径度量，图就变成了度量空间，并且图上支持的所有指标的收集将传递几何信息，可用于理解和研究图形的组合结构。在90年代中期上升之后，到目前为止，在许多情况下，图形的几何嵌入，最著名的是将嵌入到Tree-Metrics中或经典的Lebesgue序列空间中，可以提供优雅，通常是最佳的，并且在某些情况下，唯一的计算中近似算法是在计算上存在问题的问题。该提案的第一个目标是显着促进我们对有限指标嵌入性的一般问题的理解。特别是，我们将从算法的角度研究灯泡指标与瓦斯坦斯坦指标之间的联系，以及与公制的kadec-kadec-pelczynski问题相关的薄laakso结构的几何形状。 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的法定使命，并使用基金会的知识分子优点和更广泛的影响审查标准来评估值得支持。