Extremal and Probabilistic Combinatorics via Regularity and Graph Limits

PI将继续他在组合学和图论方面的研究，专注于概率和极值问题。随机结构和随机过程，虽然本身就是一个重要的研究对象，但在解决离散数学问题（包括那些陈述是纯确定性的问题）方面也非常有效。它们成功应用的一个重要领域是极值组合，广义地说，必须在给定某些组合限制的情况下最大化或最小化某个参数。一个极值问题的例子是Turan函数，一个没有固定禁止子图的超图的最大大小。这是一个基本而关键的问题，即局部限制如何影响全球结构。尽管经过了几十年的积极尝试，大多数图兰类型的问题仍然悬而未决，比如保罗·图兰在1941年提出的著名的四面体猜想。在解决这些难题的过程中，数学家们发展出了许多有用的通用技术，例如正则引理。最近的（超）图极限和标志代数的概念似乎是研究有限结构和提供处理大型离散对象的新方法的非常强大的工具。PI将研究一些组合问题，特别是寻求应用这些技术的新方法。一些有前途的方向包括图兰函数、稳定性、子图密度之间的不等式（例如，在给定阶数和大小的图中最小化f -子图的数量）、超图跳跃、定量ramsey型问题和图嵌入问题。由于图极限和标志代数都处理所研究问题的近似，一个重要的方面是开发从渐近计算获得精确结果的方法（例如，通过稳定性方法）。极值和概率组合不仅影响数学，而且影响许多其他领域，如运筹学，信息论，代码，复杂性和算法。随机图和过程已经为各种复杂系统（如Internet或社交网络）提供了成功的模型。例如，这种模型可用于估计不可能或不实际而不能直接确定的参数，并用于预测它们的未来行为。图的极限（和图的正则性）提供了一种用有限的复杂度来近似大规模对象的方法；这种方法已经在计算机科学的参数和性能测试的背景下进行了探索。PI将研究将随机性、规律性和图极限应用于组合问题的新方法。这些领域的理论发展可能具有重大的实际意义。

The PI will continue his research in combinatorics and graph theory concentrating on probabilistic and extremal questions. Random structures and processes, while being an important object of study of their own, are also very effective in solving problems of discrete mathematics including those whose statement is purely deterministic. An important area of their successful application is extremal combinatorics where, broadly speaking, one has to maximize or minimize a certain parameter given some combinatorial restrictions. One example of an extremal question is the Turan function, the maximum size of a hypergraph without some fixed forbidden subgraph. This is a fundamental and key question that asks how local restrictions can affect the global structure. Despite decades of active attempts, most Turan-type questions remain wide open, such as the famous tetrahedron conjecture made by Paul Turan back in 1941. During attacks on these difficult problems mathematicians developed a number of useful and general techniques such as, for example, the Regularity Lemma. The more recent concepts of (hyper)graph limits and flag algebras seem to be very powerful tools for studying finite structures and for providing new methods of operating with large discrete objects. The PI will work on a number of combinatorial questions, in particular seeking new ways of applying these techniques. Some promising directions include the Turan function, the stability property, inequalities between subgraph densities (for example, minimizing the number of F-subgraphs in a graph of given order and size), hypergraph jumps, quantitative Ramsey-type questions, and graph embedding problems. Since both graph limits and flag algebras deal with an approximation to the studied problem, one important aspect is to develop methods for obtaining exact results from asymptotic calculations (for example, via the stability approach).Extremal and probabilistic combinatorics impacts not only mathematics but many other areas such as operations research, information theory, codes, complexity and algorithms. Random graphs and processes have been providing successful models for various complex systems (such as the Internet or social networks). Such models can be used, for example, for estimating parameters that are impossible or impractical to be determined directly and for predicting their future behavior. Graph limits (and graph regularity) provide a method of approximating large-scale objects by those of bounded complexity; this approach has already been explored in the context of parameter and property testing in computer science. The PI will research new ways of applying randomness, regularity, and graph limits to combinatorial problems. Theoretical developments in these areas may have significant practical implications.