Problems in Ramsey theory and 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.