Problems in Ramsey theory and extremal combinatorics

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

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.