Extremal combinatorial structures and algorithms

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

This proposal concerns research in combinatorics, focussing on extremal structures and related algorithms. This area is currently very active, and the methods are central to many applications in other mathematical disciplines as well as other fields of science, such as statistical mechanics, theoretical computer science and information and coding theory. The proposer aims to study specific central problems in extremal combinatorics including the Turan problem, cycles in graphs, graph and hypergraph coloring problems, and thresholds in random graphs. Central to these problems are well-established mathematical techniques from various areas of mathematics as well as newly developed notions of pseudorandomness in graphs and hypergraphs, inequalities of concentration of measure, and martingales. For many of these topics, the proofs of the main theorems are also connected to algorithmic complexity questions, and questions about randomized algorithms and derandomization. Many of the problems proposed, such as the extremal problem for even cycles, have long been open; any new advance is likely to have a substantial theoretical impact and at least some practical consequences. While these open problems are important and clearly difficult, new methods and standard combinatorial techniques combined with some new ideas offer new hope for solving them. Extremal combinatorics is the study of mathematical structures which have constraints placed on the substructures they may contain. An extremal structure is one which satisfies those constraints, and is optimal with respect to some measure of density. For instance, one may ask for the smallest size of a code that can securely transmit a message while correcting a given number of bit errors. These extremal structures arise naturally in many areas of science. As another example, given a network one may ask for the minimum number of nodes whose failure would cause the network to disconnect. 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; as such, they have applications to theoretical computer science, information theory and statistical mechanics, to mention three areas. Further concrete examples include multiplication of large arrays of numbers for qualitative web searches -- these matrices tend to have billions of rows and columns; the RSA cryptosystem, which underpins much of modern digital security and is based strongly on the belief that factoring integers is difficult. This leads to the question of algorithmic complexity, which is related to the extremal structures: given a network, efficiently find the smallest set of nodes which disconnect the network; or given a code, efficiently decode a received message. The researcher plans to use modern combinatorial and probabilistic techniques to approach some central problems in the area and to study the practical algorithms which these methods generate. He will collaborate with PhD students and teach advanced courses on these topics.