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.

The project, in addition to advancing combinatorial research, will also help to build new bridges between combinatorics and other fields. Two aspects of the proposal, graph limits and flag algebras, are already changing the way how one approaches combinatorial problems and this new point of view may turn out to be useful in other areas. Graph limits give new ways of bringing techniques from analysis, probability, ergodic theory, and other fields into combinatorics; conversely, new combinatorial methods will also enrich other fields. Flag algebras provide a formal system for operating with limit objects, where a computer can help in finding mathematical proofs of combinatorial theorems. This novel way of using computers has already led to a number of important discoveries over a short period of time.

A great attraction of combinatorics is that many open questions have an elementary formulation and require hardly any prerequisites in order to understand them. Such problems play indispensable role in popularising mathematics and conveying the spirit and the challenges of current mathematical research to the general public.