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.