Problems in Ramsey theory and extremal combinatorics

这个项目考虑了拉姆齐理论、极值图论和组合几何中的几个问题。在解决这些问题时，将使用各种组合方法，包括概率方法、密度增量变元、分隔符方法以及几何交图和偏序集之间的联系。这些方法最近在相关问题上取得了实质性进展。这个项目的第一个主题是估计拉姆齐数。PI将致力于证明经典(完全)图和超图Ramsey数的新界，并证明稀疏图的Ramsey数的线性界。这个项目的第二个主题是Sidorenko的一个美丽猜想和相关的子图重数问题。第三个主题是得到三角形去掉引理及其变种的新的界。三角形移除引理指出，任何具有次三次数个三角形的图都可以通过去掉次二次数的边来使其不含三角形。最后，这个项目包括了一些几何图论中的极值问题，这些问题彼此密切相关。这些猜想包括：拟平面图至多有一个线性边数，平面几何对象的交图的色数作为团数的函数有界，几何交图与偏序集密切相关，几何交图有小的分隔符。以前的工作表明，这些问题及相关问题有着广泛的应用。这项工作还导致了强大的方法的发展，这些方法已被用于数学和计算机科学的许多分支。例如，以前在估计Ramsey数方面的进展导致了概率技术的发展，这些技术对理论计算机科学产生了巨大的影响，例如在随机算法的设计方面。预计在这些问题上的进一步工作将带来新的方法和应用。除了研究，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.