Problems in Ramsey theory and extremal combinatorics

拉姆齐理论和极值组合学中的问题

• 批准号: 1069197
• 负责人: Jacob Fox
• 金额: $ 24.52万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-07-01 至 2014-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1069197&HistoricalAwards=false
• 关键词: Problems; Ramsey; theory; extremal; combinatorics

This project considers several problems in Ramsey theory, extremal graph theory, and combinatorial geometry. In tackling these problems, a variety of combinatorial methods will be used including probabilistic methods, density increment arguments, separator methods, and connections between geometric intersection graphs and partially ordered sets. These methods have recently led to substantial progress on related problems. The first topic in this project is estimating Ramsey numbers. The PI will work on proving new bounds for classical (complete) graph and hypergraph Ramsey numbers, and proving linear bounds for Ramsey numbers of sparse graphs. The second topic of this project is a beautiful conjecture of Sidorenko and related subgraph multiplicity problems. The third topic is obtaining new bounds on the triangle removal lemma and its variants. The triangle removal lemma says that any graph with a subcubic number of triangles can be made triangle-free by removing a subquadratic number of edges. Finally, this project includes a number of extremal problems in geometric graph theory which are closely related to each other. These include conjectures which say that quasi-planar graphs have at most a linear number of edges, intersection graphs of planar geometric objects have chromatic number bounded as a function of their clique number, geometric intersection graphs and partially ordered sets are closely related, and geometric intersection graphs have small separators.Previous work has shown that these and related problems have a wide range of applications. This line of work has also led to the development of powerful methods which have been used in many branches of mathematics and computer science. For example, previous progress on estimating Ramsey numbers led to the development of probabilistic techniques which have had a tremendous influence on theoretical computer science, such as in the design of randomized algorithms. It is expected that further work on these problems will lead to new methods and applications.In addition to research, the PI plans to advance mathematics through education. The PI will develop undergraduate and graduate level courses which cover important topics and methods in combinatorics, with the intent of equipping students with the tools needed for quality research. The materials will be made openly available online. Some of the topics in these courses will be related to the problems in this project. The PI also plans to advise undergraduate and graduate students on research in combinatorics related to the topics of this project. The PI will continue to write research papers, organize seminars, and give a wide range of talks, from research talks for experts to introductory talks meant to encourage students into studying mathematics and science.

这个项目考虑了拉姆齐理论、极值图论和组合几何中的几个问题。在解决这些问题时，将使用各种组合方法，包括概率方法，密度增量参数，分隔符方法，以及几何相交图和偏序集之间的连接。这些方法最近在相关问题上取得了实质性进展。这个项目的第一个主题是估计Ramsey数。PI将致力于证明经典（完全）图和超图Ramsey数的新界限，并证明稀疏图的Ramsey数的线性界限。本项目的第二个主题是Sidorenko的一个美丽猜想和相关的子图多重性问题。第三个主题是获得三角形移除引理及其变体的新界。三角形移除引理说，任何具有次立方数量三角形的图都可以通过移除次二次数量的边而成为无三角形的。最后，这个项目包括几何图论中的一些极值问题，这些问题彼此密切相关。这些问题包括：拟平面图的边数至多为线性，平面几何对象的交图的色数是其团数的函数，几何交图与偏序集密切相关，几何交图有小分隔符等，这些问题及相关问题有着广泛的应用.这一工作也导致了强大的方法的发展，这些方法已被用于数学和计算机科学的许多分支。例如，先前在估计拉姆齐数方面的进展导致了概率技术的发展，这些技术对理论计算机科学产生了巨大的影响，例如在随机算法的设计中。预计对这些问题的进一步研究将导致新的方法和应用。除了研究，PI计划通过教育促进数学。PI将开发本科和研究生水平的课程，涵盖组合学中的重要主题和方法，旨在为学生提供高质量研究所需的工具。这些材料将在网上公开提供。这些课程中的一些主题将与本项目中的问题相关。PI还计划为本科生和研究生提供与本项目主题相关的组合学研究方面的建议。PI将继续撰写研究论文，组织研讨会，并进行广泛的演讲，从专家的研究演讲到旨在鼓励学生学习数学和科学的介绍性演讲。