Extremal graph theory, graph limits, and algebraic invariants

在这个项目中，PI的目标是使用代数和分析工具研究非常大的网络。像互联网、分子晶格和社交网络（如Facebook）这样的大型网络自然出现在现实生活的许多不同领域。PI旨在从一个新的角度来看待这些：我们将它们视为无限物体的近似值。对于分子晶格来说，这是一种非常自然的方法，但通过最近发展的稀疏图收敛理论，我们可以解决更广泛的问题，在数学、统计物理和计算机科学之间建立新的联系。PI将调查两个本质上不同但仍然相关的主题。第一部分研究图的代数不变量的极值问题，重点研究图的猜想极值不是有限的问题。尽管缺乏有限的极值解，但使用最近出现的Benjamini- Schramm收敛语言，人们可以找到并分析极值解。这就导致了有限图上新的渐近结果。第二个主题是用图极限理论和解析与代数组合学研究某些特殊的无限图和格。一般的主题是考虑一个代数性质的图不变量，并使用分析工具分析它的极限行为。不变量通常来自图多项式，如匹配多项式、色多项式和独立多项式，并且与统计力学有各种联系。

In this project, the PI aims to study very large networks using algebraic and analytic tools. Large networks like the Internet, molecular lattices and social networks (such as Facebook) naturally arise in many different areas of real life. The PI aims to look at these from a new perspective: we consider them as approximations of an infinite object. For molecular lattices this is a very natural approach, but via a recently developed theory of sparse graph convergence we can tackle a much broader class of problems, creating new links between mathematics, statistical physics and computer science.The PI will investigate two essentially different, but still related topics. The first one is the study of extremal values of algebraic invariants of graphs with a special emphasis on those problems where the conjectured extremal graphs are not finite. Despite the lack of finite extremal solutions, using the recently emerging language of Benjamini--Schramm convergence, one can find and analyze the extremal solutions. This then leads to new asymptotic results on finite graphs. The second topic is the study of certain special infinite graphs and lattices via graph limit theory and analytic and algebraic combinatorics. The general theme is to consider a graph invariant of algebraic nature and analyze its limiting behaviour using analytic tools. Often the invariants come from graph polynomials like the matching, chromatic and independence polynomials and have various ties to statistical mechanics.