权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Analytic methods for large discrete structures

大型离散结构的分析方法

基本信息

批准号：
EP/M025365/1
负责人：
Daniel Kral
金额：
$ 38.38万
依托单位：
University of Warwick
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2015
资助国家：
英国
起止时间：
2015 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FM025365%2F1
关键词：
Analytic methods large discrete structures

项目摘要

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.

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