Graph Limits and Measurable Graphs

了解大型现实生活网络的结构和属性已成为我们这个时代最重要的科学挑战之一。大型网络在自然科学和社会科学中无处不在，我们可以获得越来越多的关于它们的数据。然而，大多数现有的分析这些数据的方法对于即使是中等规模的网络也太慢了。因此，需要设计出新的、强大的网络分析工具。构建新工具的一种方法是提高我们对大型网络的底层结构的理解。这种方法在具有相对较多连接的网络(所谓的密集网络)的情况下取得了巨大的成功。然而，大多数真实世界的网络并不属于这一类(它们是所谓的稀疏的)，我们对它们的结构属性的了解仍然相当有限。这个项目的目标是通过研究网络之间的相似性，并通过使用连续模型--所谓的图极限--来逼近大型网络，从而促进对大型稀疏网络的理解。事实证明，在密集网络的情况下，这种方法非常成功。在稀疏案例中进展缓慢，主要是因为相似性的“正确”概念似乎难以捉摸，而且随着时间的推移，出现了许多不同的概念，它们之间的关系仍然不清楚。该项目将专注于图的极限，即定义在概率度量空间上的网络，即所谓的图。它将研究关于这类物体的经典图论概念。为数不多的已知结果表明，与经典图形相比，图形经常显示出惊人的差异。然而，人们经常可以找到自然的假设，在这种假设下，经典结果扩展到可测量的背景下，而不做任何改变。该项目的中心动机问题是有限图的图形的可逼近性。为此，我们将详细探讨图的各种组合和代数性质，以便与有限图进行比较。组合方面包括理解图论中关于匹配、顶点着色和边着色的存在的标准定理如何推广到图中。代数方面包括对图形光谱特性的研究。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Understanding the structure and properties of large real-life networks has become one of the most important scientific challenges of our time. Large networks are ubiquitous in both the natural and social sciences and we have access to more-and-more data about them. However, most existing methods for analyzing this data are too slow for even moderately large networks. Hence the need to devise, new, robust tools for network analysis. One way of building new tools is to advance our understanding of the underlying structure of large networks. This approach has led to tremendous success in the case of networks with relatively many connections (so called dense networks). However, most real-word networks do not fall into this category (they are so-called sparse), and our understanding of their structural properties remain rather limited. The goal of this project is to advance the understanding of large sparse networks through the study of similarities between networks, and via the use of continuous models - so called graph limits - to approximate large networks. This approach has proved extremely successful in the case of dense networks. Progress in the sparse case has been slow mainly because the "right" notion of similarity seems elusive, and a host of different concepts have emerged over time whose relationship to each other remains unclear. The project will focus on the graph limits, networks defined on probability measure spaces, so-called graphings. It will investigate classical graph theoretic notions on such objects. The few known results indicate that graphings frequently exhibit surprising differences compared to classical graphs. Yet, one can often find natural assumptions under which classical results extend to the measurable context without any change. The central motivating question of the project is the approximability of graphings by finite graphs. To this end, various combinatorial and algebraic properties of graphings will be explored in detail to allow comparison to finite graphs. The combinatorial aspects include understanding how standard theorems in graph theory about the existence of matchings, vertex- and edge-colorings generalize to graphings. Algebraic aspects include the study of spectral properties of graphings.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.