Analytic methods for large discrete structures

本研究属于离散数学范畴。该项目解决了最近出现和迅速发展的组合极限理论中的几个基本问题。这一理论使人们更好地理解了组合学和理论计算机科学中的重要概念，如正则性和性质测试，它提供了用于解决极值组合学中许多长期存在的开放性问题的分析工具，并在分析学、组合学、遍历论、群论和概率论之间开辟了新的联系。组合极限理论快速发展的原因之一来自计算机科学，其中诸如互联网连接图或社交网络图（例如Facebook， LinkedIn）的结构是巨大的，组合极限理论的工具可以通过分析对象来近似这些结构。我们计划扩展标志代数方法在极值组合中的可能应用范围，将该方法应用于新的设置，特别是与Turán密度相关的设置，并将该方法应用于极值组合中的特定问题。我们还将使用标志代数参数来获得有限强制图极限与极值组合问题最优解之间关系的新见解。密集和稀疏离散结构的极限相关的概念在很大程度上是分开发展的，并试图通过模型理论启发的FO收敛概念来弥合它们之间的差距。我们计划探索用相应的解析对象（建模）来表示FO收敛序列的极限。我们的目的也是利用所获得的知识来提供一个更强大的收敛概念，这将对较小的局部修改不那么敏感。

The proposed research belongs to discrete mathematics. The project addresses several fundamental questions in the recently emerged and rapidly evolving theory of combinatorial limits. This theory led to a better understanding of important concepts in combinatorics and theoretical computer science, e.g. regularity and property testing, it provided analytic tools that were used to solve many long standing open problems in extremal combinatorics, and it opened new links between analysis, combinatorics, ergodic theory, group theory and probability theory. One of the reasons for the rapid growth of the theory of combinatorial limits comes from computer science where structures such as the graph of internet connections or graphs of social networks (e.g. Facebook, LinkedIn) are of enormous size and the tools from theory of combinatorial limits can be used to approximate these structures by analytic objects.We plan to extend the range of possible applications of the flag algebra method in extremal combinatorics by adopting the method to new settings, in particular those related to Turán densities, and give applications of the method to specific problems from extremal combinatorics. We will also use the flag algebra arguments to gain new insights in the relation between finitely forcible graph limits and optimal solutions of extremal combinatorics problems.The concepts related to the limits of dense and sparse discrete structures were developed to a large extent separately and an attempt to bridge the gap between them was made through the model theory inspired notion of FO convergence. We plan to explore the limits of representing FO convergent sequences by the corresponding analytic objects (modellings). Our intention is also to use the knowledge gained to provide a more robust notion of convergence which would be less sensitive to minor local modifications.