Ramsey and Turan Type Problems

拟议的项目涵盖了极值组合学中的几个重要主题。第一组问题涉及拉姆齐理论。这里的一个目的是理解3-一致超图的对角线Ramsey数的渐近行为。目前这些数字的上下限之间存在一个指数级的差距，缩小这一差距是该领域最具挑战性的问题之一。作者还计划研究稀疏图的Ramsey数，即每个子图都有有界平均度的图。Burr和Erdos在35年前猜想，这些图的Ramsey数与它们的顶点数成线性增长。这是图拉姆齐理论中备受关注的核心问题之一。该提案中的另一组问题涉及图兰式问题。特别是，Pi计划继续他40年前关于二部图的Turan数的猜想的工作，其中每个子图至多有r个度顶点。他还计划研究Erdos-Simonovits和Sidorenko的美丽猜想，即二部图H在n点图中的拷贝数至少与具有相同边密度的随机n点图中的拷贝数一样多。这一重要猜想与矩阵理论、马尔可夫链、图极限和拟随机性有关。组合学是数学的一个分支，主要研究离散对象及其性质。虽然组合数学可能和人类的算术能力一样古老，但该领域在过去50年里经历了巨大的发展，是当今数学中最现代的学科之一，与不同学科和各种实际应用有许多联系，从设计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.