Extremal and Probabilistic Combinatorics

极值与概率组合学PI计划继续研究极值与概率组合学之间的相互作用。极值组合学的现代趋势之一是研究一般性质和大族组合结构的极值和概率方面。派是这一趋势的主要倡导者之一，几个主要结果归功于他和他的合作者。到目前为止出现的实质性理论延续了50年前开始的理论，但远远超出了经典成果。其目的是确定图(或超图)的遗传性的精细结构，该遗传性对于给定的增长率下界是极小的。希望得到足够精确的刻画，从而得到随机图的广义色数的良好估计。所使用的方法是复杂的极值论点和基于Erdos-Stone定理、Ramsey定理的变体、Szmeredi正则性引理和度量集中不等式的概率方法的令人兴奋的结合。PI将与托马森、Bright twell、Leader、Scott、Balogh、Weinreich和其他人在该项目上进行合作。PI还将致力于其他几个相关项目：与Riordan关于有色图和胖图的不变量和多项式的研究，与Balister和Stacey关于渗流的研究，与Aratia和Sorkin关于排序的问题，与Borgs，Chayes，Kim和Wilson关于随机组合结构中的相变的研究。PI将研究的问题是极值和概率组合学的主要问题。除了它们的内在意义外，这些问题还与计算机科学、统计物理和DNA测序中的问题有关。

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.