Extremal Combinatorics and Applications

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

Extremal combinatorics is an important area of discrete mathematics. The mathematical methods in extremal combinatorics are now central tools in combinatorics, and give rise to many applications in other areas of mathematics as well as other fields of science, such as statistical mechanics, biology, theoretical computer science and information and coding theory. The proofs of the central theorems are also connected to algorithmic complexity questions, as well as questions on randomized algorithms and derandomization. For instance, given a network one may ask for the minimum number of nodes whose failure would cause the network to disconnect, and how efficiently one can exhibit such a set of nodes -- this is one of the central topics in graph theory. These questions often lie at the heart of digital and communication security, web searching, reliable data transmission, network dynamics, and the spread of infectious disease or information, and so on.This award supports research in combinatorics, focusing on the very active area of extremal and probabilistic combinatorics. The aim is to study specific central problems in extremal combinatorics, such as the Turan and Ramsey problems for both graphs and hypergraphs, matching and coloring problems and the extension of these problems into the context of models of random graphs and hypergraphs. In recent years, there has been a sharp increase in the number of new tools available for studying these problems, including the various notions of pseudorandomness in graphs and hypergraphs, martingale concentration inequalities and probabilistic sieving methods, as well as regularity lemmas, to mention a few. The problems which the PI propose to study, such as the extremal problem for bipartite graphs, remain open, and any new advance is likely to have a substantial theoretical impact and practical consequences. While these open problems are important and clearly difficult, the new methods and combinatorial techniques mentioned above together with new ideas look very promising for the resolution of these problems.