###Extremal graph theory
Project ID: 2228bd1178 (You will need this ID for your application)
Research Theme: Mathematical Sciences
UCL Lead department: Mathematics
Lead Supervisor: Shoham Letzter
Project Summary:
In extremal graph theory, one studies how large, or how small, certain graph parameters can be, if the graph is to satisfy certain conditions.
In this project, we focus on properties involving the containment of cycles. Relevant classical results include Dirac’s theorem, which determines the least minimum degree condition guaranteeing a Hamilton cycle (namely a cycle that goes through all vertices in the graph), and Turán-type results determine (for odd lengths) or estimate (for even lengths) the minimum number of edges guaranteeing the containment of a cycle of a certain length.
The project could go in various directions. For example, one could investigate Turán-type problems for (tight) cycles in hypergraphs; here a hypergraph is a generalisation of a graph, where edges can have more than two vertices. Alternatively, we could look at minimum degree conditions forcing a regular oriented graph (which is a graph where each edge receives a direction) to have a decomposition into Hamilton cycles. It is also interesting to find the minimum number of cycles needed to cover the vertices of a regular graph of a given degree, either in the directed or the undirected case.
Methodology will be likewise varied. Some examples of relevant methods include: the regularity method, the absorption method, and expanders.
In summary, the goal would be to explore external problems related to cycles, to learn the relevant methodology, and to solve some open problems in this direction.
The importance of the project lies both in the problems considered, which have a strong classical foundation and are also very trendy, and in the methods learned.
An ideal candidate would be one with a strong background in combinatorics, and the desire and ability to deepen their knowledge in the direction proposed.