Ramsey and Turan Type Problems

提议的项目涵盖了极值组合学中的几个重要主题。第一组问题与拉姆齐理论有关。这里的一个目标是理解3-一致超图的对角拉姆齐数的渐近行为。在这些数字的当前上限和下限之间存在一个指数差距，缩小这一差距是该领域最具挑战性的问题之一。作者还计划研究稀疏图的Ramsey数，即每个子图的平均度有界的图。35年前，Burr和Erdos推测，这些图的拉姆齐数在顶点数量上呈线性增长。这是图拉姆齐理论中备受关注的核心问题之一。本建议中的另一组问题涉及图兰类型的问题。特别是，PI计划继续研究Erdos关于二部图的图兰数的40年猜想，其中每个子图的顶点度最多为r。他还计划研究Erdos- simonovits和Sidorenko的美丽猜想，该猜想指出n顶点图中二部图H的副本数量至少与具有相同边密度的随机n顶点图一样大。这一重要猜想与矩阵理论、马尔可夫链、图极限和拟随机性有关。组合学是研究离散对象及其性质的数学分支。虽然组合学可能与人类计数能力一样古老，但该领域在过去五十年中经历了巨大的增长，是当今数学中最现代的领域之一，与不同学科和各种实际应用有许多联系，从设计VLSI芯片到建模复杂的社会网络。在任何六个人的公司中，是否有三个人彼此都认识，或者彼此都不熟悉？任何平面地图上的国家最多可以用四种颜色上色，以使有共同边界的两个国家的颜色不相同吗？如果一个复杂电话网络的每条链路都以p的概率失效，那么Alice不能和她的朋友Bob通过电话交谈的概率是多少？这类问题是现代组合学的核心，说明了PI计划考虑的各种研究课题。

The proposed project covers several important topics in Extremal Combinatorics. The first group of questions concerns Ramsey Theory. One goal here to understand the asymptotic behavior of diagonal Ramsey numbers of 3-uniform hypergraphs. There is a gap of one exponential between the current upper and lower bounds for these numbers and closing this gap is one of the most challenging questions in the area. The author also plans to study the Ramsey numbers of sparse graphs, i.e., graph in which every subgraph has bounded average degree. It was conjectured 35 years ago by Burr and Erdos that Ramsey numbers of these graphs grow linearly in the number of their vertices. This is one of the central problems in Graph Ramsey Theory which attracted a lot of attention. Another set of questions in this proposal deals with Turan-type problems. In particular PI plans to continue his work on the 40 year old conjecture of Erdos on the Turan numbers of bipartite graphs, in which every subgraph has vertex of degree at most r. He also plans to study the beautiful conjecture of Erdos-Simonovits and Sidorenko which states that the number of copies of bipartite graph H in a n-vertex graph is at least as large as in the random n-vertex graph with the same edge density. This important conjecture has connection to matrix theory, Markov chains, graph limits and quasirandomness.Combinatorics is a branch of mathematics focusing on the study of discrete objects and their properties. Although Combinatorics is probably as old as the human ability to count, the field experienced tremendous growth during the last fifty years and is one of the most modern in today's Mathematics, with numerous connections to different disciplines and various practical applications, ranging from designing VLSI chips to modeling complex social networks. Is it true that in any company of six people there are three who all know each other, or alternatively are all unfamiliar with each other? Can the countries of any planar map be colored with at most four colors so that no two countries that share a common boundary have the same color? If each link of a complex telephone network fails with probability p, what is the probability that Alice will not be to have a phone conversation with her friend Bob? Questions of this type are in the heart of modern Combinatorics and illustrate various research topics which PI plans to consider.