Ramsey and Turan Type Problems

拉姆齐和图兰类型问题

• 批准号: 1101185
• 负责人: Benjamin Sudakov
• 金额: $ 30.17万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-07-01 至 2014-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1101185&HistoricalAwards=false
• 关键词: Ramsey; Turan; Type; Problems

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.

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