Extremal graph theory, Ramsey theory and additive combinatorics

Lead Research Organisation: University of Cambridge
Department Name: Pure Maths and Mathematical Statistics

Abstract

In the first year of my PhD I was working on three topics in combinatorics (also known as discrete mathematics). One of them is extremal graph theory which is concerned with determining the maximal number of edges in a graph which does not contain a given subgraph. The second one is Ramsey theory. Roughly speaking, this field focuses on finding structures in a graph or its complement. Finally, the third area is additive combinatorics, which investigates subsets of groups. (Groups are objects on which addition can be defined, such as the integers or real numbers.) This last project also has significance in theoretical computer science.

Together with my supervisor, Timothy Gowers, we have managed to establish publishable results in all three of these areas. A common technique which was used heavily in these projects is the so-called probabilistic method, which is a powerful tool allowing us to find objects with certain properties by randomly picking one object of all the available ones.

In the future I will be aiming to solve further open problems in the three areas mentioned above.

Publications

10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/N509620/1 01/10/2016 30/09/2022
1951090 Studentship EP/N509620/1 01/10/2017 30/09/2020 Oliver Janzer
 
Description The goal in our project was to prove deep and interesting new results in the field of Discrete Mathematics, more specifically in the areas Extremal Graph Theory, Ramsey Theory and Additive Combinatorics. We have managed to achieve this, and in fact we have greatly exceeded our expectations in that we have been able to obtain more important results than what we have originally anticipated. Here I briefly describe our three most important achievements.

The first achievement is an improved bound on a well-studied function (called the Erdos-Rogers function), which is a generalization of the famous Ramsey numbers. Together with my PhD advisor, we were able to obtain better estimates for this function, answering a central open problem in Ramsey Theory.

Secondly, in individual work, I have managed to relate two central notions of tensor ranks to each other by showing that the partition rank of a tensor is bounded by a polynomial in the analytic rank of the same tensor. This improves work by leading researchers in Additive Combinatorics.

Finally, my most important contribution is to the area of Extremal Graph Theory. The main question in this field is to estimate, for a given graph H, the maximum number of edges that an n-vertex graph can have if it does not contain H as a subgraph. The question is particularly interesting when H is a bipartite graph, in which case the order of magnitude of this number is not well understood. I have been able to develop a new method for getting tight bounds for this number for a wide range of graphs H, e.g. when H is a subdivision of the complete graph or the complete bipartite graph. I used this new approach to answer many important open problems in the area. Several leading researchers have since adapted my method to prove additional interesting results. I have posed new conjectures as well, which motivated further work by other mathematicians.
Exploitation Route The research done by this funding is theoretical in nature, so the main applications are in Mathematics itself. My publications have attracted much interest from the Discrete Mathematics community; indeed many of my papers have got multiple citations by leading researchers in the field. People have been studying and using my methods to prove further theorems, especially in Extremal Graph Theory. Researchers also wrote papers on conjectures that I raised.

While my results are theoretical, graphs are used in several fields of sciences, such as Computer Science and Genetics. Thus, my work may provide the foundation for more practical research in the future.
Sectors Other