Analytic methods for large discrete structures

所提出的研究属于离散数学。该项目解决了最近出现并迅速发展的组合极限理论中的几个基本问题。这一理论使人们更好地理解了组合学和理论计算机科学中的重要概念，如正则性和性质测试，它提供了分析工具，用于解决极值组合学中许多长期悬而未决的问题，并开辟了分析、组合学、遍历理论、群论和概率论之间的新联系。组合极限理论迅速发展的原因之一来自计算机科学，其中互联网连接图或社交网络图(如Facebook、LinkedIn)的结构是巨大的，组合极限理论的工具可以用解析对象来逼近这些结构。我们计划将标志代数方法的可能应用范围扩展到新的环境，特别是与图兰密度相关的环境，并给出该方法在极端组合数学的具体问题中的应用。我们还将使用标志代数论证来获得极值组合问题的有限强制图极限与最优解之间的关系的新见解。与稠密和稀疏离散结构极限相关的概念在很大程度上是分开发展的，并试图通过模型理论启发的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.