Extremal and Probabilistic Combinatorics

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

Extremal and Probabilistic CombinatoricsThe PI plans to continue his work on the interplay between extremal and probabilistic combinatorics. One of the modern trends in extremal combinatorics is the study of extremal and probabilistic aspects of general properties and large families of combinatorial structures. The PI is one of the main advocates of this trend, and several of the main results due to him and his collaborators. The substantial theory that has emerged so far continues the theory started fifty years ago, but goes way beyond the classical achievements. The aim is to determine the fine structure of a hereditary property of graphs (or hypergraphs) that is minimal for a given lower bound on the rate of growth. The hope is to obtain characterizations that are precise enough to lead to good estimates of the generalized chromatic numbers of random graphs. The methods to be employed are an exciting blend of intricate extremal arguments and probabilistic methods based on the Erdos-Stone theorem, variants of Ramsey's theorem, Szemeredi's regularity lemma, and concentration of measure inequalities. The PI will collaborate with Thomason, Brightwell, Leader, Scott, Balogh, Weinreich, and others on the project. The PI will work on several other related projects: with Riordan on invariants and polynomials of colored graphs and fat graphs, with Balister and Stacey on percolation, with Arratia and Sorkin on problems related to sequencing, and with Borgs, Chayes, Kim and Wilson on phase transitions in random combinatorial structures.The problems to be studied by the PI are major problems of extremal and probabilistic combinatorics. In addition to their intrinsic significance, the problems are relevant to questions in computer science, statistical physics, and DNA sequencing.