Extremal Combinatorics

点击翻译按钮获取中文摘要

Extremal Combinatorics studies relations between various parameters of discrete structures. This area experienced a remarkable growth in the last few decades. Various aspects of Computer Science and Operations Research motivated by large-scale practical problems have been relying on more and more sophisticated combinatorial techniques and have posed a whole array of new challenging problems in Discrete Mathematics. At the same time, the development of powerful and deep mathematical methods has greatly expanded the horizon of combinatorial questions that can be approached now, meeting many of the above challenges. The project will concentrate on central questions of Extremal Combinatorics. Two examples are the the Turan function that asks how local restrictions can affect the global size of a hypergraph and the Ramsey theory that investigates whether large structures contain highly ordered substructures. These problems seem to be notoriously difficult and even some basic questions remain open. The previous attempts, although not completely successful, led to a number of useful techniques and insights. Some recent developments (such as hypergraph regularity, graph limits, and flag algebras) give us new powerful tools that may be instrumental in obtaining progress on these problems. The project aims at achieving a better understanding of these areas and developing generally useful methods and techniques.